在单程中找到第K个最大数字而不存储整个数组

Question

我想到的算法是

• 保持MaxHeap的大小为K.
• 插入每个元素
• 如果堆已满,则删除较小的值
• 最后,Kth max是MaxHeap中较小的一个

这将给我O(NlogK).有更好的算法吗？我不能快速选择,因为数组不能存储在内存中.

Answer 1

根据您的内存限制,您可以使用中位数中值算法的修改版本来解决O(n)时间和O(k)空间中的问题.

这个想法如下.在内存中维护一个大小为2k的数组.用数组中的前2k个元素填充此缓冲区,然后在其上运行中位数中值算法,将最大的k个元素放在数组的前半部分中,将最小的k个元素放在后半部分中.然后,丢弃最小的k个元素.现在,将下一个k元素加载到数组的后半部分,使用中位数中值算法再次将前k个元素放在左侧,将底部k个元素放在右侧.如果你在整个数组中迭代这个过程 - 用数组中的下一个k元素替换缓冲区的后半部分,然后使用中位数中位数将那些中位数的k移动到左半部分 - 然后在最后你将在数组的左半部分有前k个元素.找到最小的那些(在O(k)时间内)将给出第k个最大元素.

总的来说,你最终使用大小为O(k)的数组对中位数算法进行O(n/k)调用,这是对O(k/k)时间算法的O(n/k)调用,对于O(n)的净运行时间.这与最后一步相结合,在O(n + k)= O(n)时间内运行.此外,由于中位数中位数的内存使用量为O(k),并且由于您有一个大小为O(k)的缓冲区,因此仅使用O(k)内存.换句话说,它比min-heap解决方案渐近地快,并且在内存中渐近等效.

希望这可以帮助!