arrays - 在不存储整个数组的情况下单次查找第 K 个最大的数字

Question

我想到的算法是

• 保持一个大小为 K 的 MaxHeap
• 插入每个元素
• 如果堆已满则丢弃较小的值
• 最后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) 的算法的 O(n/k) 次调用k) 时间，对于 O(n) 的净运行时间。这与最后一步相结合，运行时间为 O(n + k) = O(n)。此外，由于中位数步骤的内存使用量为 O(k)，并且由于周围有大小为 O(k) 的缓冲区，因此这仅使用 O(k) 内存。换句话说，它比最小堆解决方案渐近更快，并且在内存中渐近等效。<​​/p>

希望这对您有所帮助!