如何找到在一个文本文件ñ最长的线路，并打印到stdout？ [英] How to find N longest lines in a text file and print them to stdout?

问题描述

第一行包含数字N后面多行的值。 我可以解决这个问题，以便为n ^ 2算法。有人建议可以更好的呢？

解决方案

1. 您可以使用一个最小堆和做它在为O（n *（日志（N）））：

    堆=新闵堆（N）
      的foreach行文字：
           如果长度（线）GT; heap.min（）：
           heap.pop（）
           heap.insert（线）
      的foreach线堆：
           打印到标准输出：行。
    

2. 它也可以在O（n）的使用选择（N）（其选择第N号），接着通过围绕第N号的分区（完成其中安排所有的大小为大于或等于第N数其一侧）。

     I =选择（系，N）
      分区（线，i）的
      因为我要的大小（行）：
            打印到标准输出：行[I]
    

The first line contains the value of the number 'N' followed by multiple lines. I could solve it in order of n^2 algorithm. Can someone suggest a better one?

解决方案

1. You can use a minimum-heap and do it 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 to stdout: line.
   

2. it could also be done in O(n) using Select(N) (which selects the Nth number) followed by partition around the Nth number (which arranges all the with size larger or equal to the Nth number to one side of it).

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

这篇关于如何找到在一个文本文件ñ最长的线路，并打印到stdout？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！