如何找到在一个文本文件ñ最长的线路,并打印到stdout?文本文件、最长、线路、stdout

2023-09-11 23:04:21 作者:逢场作戏

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

解决方案

您可以使用一个最小堆和做它在为O(n *(日志(N))):

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

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

  I =选择(系,N)
   分区(线,i)的
   因为我要的大小(行):
         打印到标准输出:行[I]
 
怎样在word文档中一次过 查找所有同一个字并标记

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?

解决方案

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.

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]

 
精彩推荐
图片推荐