给定一个数字流，您将如何跟踪第 1,000,000 个最大的数字？
我在面试中被问到这个问题。
最佳答案
一种方法是保留 minimum heap ，并将堆的大小限制为 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)
关于algorithm - 给定一个数字流，你将如何跟踪第 1,000,000 个最大的数字？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15884568/