algorithm - 如何在文本文件中找到 N 最长的行并将它们打印到标准输出？

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. 也可以使用 Select(N)(选择第 N 个数字)在 O(n) 中完成，然后围绕第 N 个数字进行分区(将所有大小大于或等于第 N 个数字的数字排列到它的一侧)。

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