第一行包含数字“N”的值,后跟多行。 我可以按照 n^2 算法的顺序解决它。有人可以推荐更好的吗?
最佳答案
您可以使用最小堆并在 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.
也可以使用 Select(N)(选择第 N 个数字)在 O(n) 中完成,然后围绕第 N 个数字进行分区(将所有大小大于或等于第 N 个数字的数字排列到它的一侧)。
i = Select(lines, N) partition(lines, i) for i to size(lines): print to stdout: lines[i]
关于algorithm - 如何在文本文件中找到 N 最长的行并将它们打印到标准输出?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5960169/