algorithm - 是否有可能从 n 个未排序的整数中找到时间复杂度 O(n) 和空间复杂度 O(k) 的 k 个最大数？

Question

我知道我们可以通过两种方式从 n 个未排序的整数中找到 k 大的数:

1. 使用quick-select之类的算法找到第K大的数，然后我们就可以得到第k大的数。时间复杂度O(n)，空间复杂度O(n)
2. 使用堆来存储 k-最大的数字并迭代 n 个整数，然后将适当的整数添加到堆中。时间复杂度O(nlogk)，空间复杂度O(k)

假设 n 个整数在一个流中，我们不能随机访问它们

我想知道是否有可能从时间复杂度 O(n) 和空间复杂度 O(k) 的 n 个未排序的整数中找到 k 个最大的数？

Answer 1

是的。用 k 个元素填充堆后，不是在每次插入后从堆中逐出一个元素，而是在每 k 次插入后从堆中逐出 k 个元素。然后您不再需要堆结构——只需每次选择即可。