algorithm - How to find N longest lines in a text file and print them to stdout? -

algorithm - How to find N longest lines in a text file and print them to stdout? -

the first line contains value of number 'n' followed multiple lines. solve in order of n^2 algorithm. can suggest better one?

you can use minimum-heap , in o(n*(log(n))):

   heap = new min-heap(n)    foreach line in text:         if length(line) > heap.min():         heap.pop()         heap.insert(line)    foreach line in heap:         print stdout: line.

it done in o(n) using select(n) (which selects nth number) followed partition around nth number (which arranges size larger or equal nth number 1 side of it).
```
   = select(lines, n)    partition(lines, i)    size(lines):          print stdout: lines[i] 
```

Comments