我想到的算法是
- 保持大小为 K 的最大堆
- 插入每个元素
- 如果堆已满，则丢弃较小的值
- 最后，第K个max是MaxHeap中较小的一个
这将给我 O(NlogK)。有更好的算法吗？我无法进行快速选择，因为数组无法存储在内存中。
根据您的内存限制，您可以使用中位数算法的修改版本来解决 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) 次调用，净运行时间为 O(n)。这与最后一步相结合，运行时间为 O(n + k) = O(n)。此外，由于中位数步骤的内存使用量为 O(k)，并且由于周围有一个大小为 O(k) 的缓冲区，因此仅使用 O(k) 内存。换句话说，它比最小堆解决方案渐近更快，并且在内存中渐近等效。
希望这可以帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
