如何在文本文件中找到N个最长的行并将它们打印到stdout？

Question

第一行包含数字'N'的值,后跟多行.我可以按n ^ 2算法的顺序解决它.有人可以提出更好的建议吗？

Answer 1

1. 您可以使用最小堆并在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 to stdout: line.
   

2. 它也可以在O(n)中使用Select(N)(选择第N个数字),然后在第N个数字周围进行分区(将所有大小或者等于第N个数字排列到它的一侧).

      i = Select(lines, N)
      partition(lines, i)
      for i to size(lines):
            print to stdout: lines[i]