能否在时间复杂度为O(n)和空间复杂度为O(k)的情况下找到n个未排序整数中的前k大数？

Question

我知道我们可以用两种方法从 n 个未排序的整数中找到 k 个最大的数：

1. 使用类似于快速选择的算法来找到第 k 大的数字，然后我们可以得到 k 个最大的数字。时间复杂度为 O(n)，空间复杂度为 O(n)
2. 使用堆来存储 k 个最大的数字，并迭代遍历 n 个整数，然后将适当的整数添加到堆中。时间复杂度为 O(nlogk)，空间复杂度为 O(k)

假设这 n 个整数都在流中，我们没有随机访问它们的能力。

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

- lzy9059

---

为什么您认为快速选择的空间复杂度为O(N)。它具有O(1)的附加内存复杂度（假设您可以重新排列输入）。 - Ivaylo Strandjev

可以完成这个任务。请参阅http://link.springer.com/chapter/10.1007%2FBFb0015429。使用此算法，您可以在线性时间内仅使用常数数量的附加变量找到第k大的数字。 - Yu-Han Lyu

Answer 1

没错，这就是所谓的堆排序。在堆中填充k个元素后，每次插入k个元素之后，从堆中驱逐k个元素，而不是每次插入一个元素后从堆中驱逐一个元素。然后你就不再需要堆结构了——每次只需选择即可。

- David Eisenstat

---

这听起来不错。在我看来，你实际上并不需要一个堆，只需要一个有2k个位置的数组即可。 - Juan Lopes

Answer 2

冒泡排序的k次迭代会在数组末尾给出k个最大的元素，时间复杂度为O(nk)。

- Alok Kumar Rai