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

Question

第一行包含数字“N”的值，后跟多行。 我可以按照n^2算法的顺序解决它。有人可以建议一个更好的吗？

Answer 1

1. 您可以使用最小堆并在 O(n*(log(N))) 内完成：

    堆 = new Min-Heap(N)
      foreach 文本行：
           如果长度（线）>堆.min():
           堆.pop()
           堆.插入（行）
      foreach 堆中的行：
           打印到标准输出：行。
   

2. 它也可以使用 Select(N) 在 O(n) 中完成（选择第 N 个数字），然后围绕第 N 个数字进行分区（将所有大小大于或等于第 N 个数字的元素排列到其一侧）。

    i = 选择（行，N）
      分区（行，i）
      对于我的大小（行）：
            打印到标准输出：lines[i]