1

给定一串数字，您将如何跟踪第 1,000,000 个最大的数字？

我在一次采访中被问到这个问题。

4

2 回答 2

14

一种方法是保持最小堆，并将堆的大小限制为 1,000,000。虽然堆还没有达到 1,000,000 个项目，但我们会将流中的每个新项目添加到我们的堆中。当堆满时，我们会将流中的每个新项与堆中的最小值进行比较，如果大于最小值，我们将弹出最小值并插入新项。这样，堆的最小项始终是第 1,000,000 个最大值。

伪代码示例：

Handle_Stream_Item(item):
  if(MinHeap.size < 1000000):
    MinHeap.insert(item)
  else if (item > MinHeap.min()):
    MinHeap.extractMin()
    MinHeap.insert(item)
于 2013-04-08T16:52:42.917 回答
0

从流中读取每个数字时，将其添加到 B-TREE 结构中。

https://en.wikipedia.org/wiki/B-tree

从百万和第一个数字开始，添加新数字后，从 B-TREE 中删除最右边（即最大）的数字。

在任何时候，B-TREE 中最右边的数字都是您想要的数字。

于 2013-04-08T16:51:56.783 回答