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

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

使用快速选择之类的算法查找第K个最大数字，然后我们可以获得第k个最大数字。时间复杂度为O(n)，空间复杂度为O(n)

使用堆存储k个最大的数字并迭代n个整数，然后将适当的整数添加到堆中。时间复杂度为O(nlogk)，空间复杂度为O(k)

假设n个整数在流中，并且我们没有对它们的随机访问

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

最佳答案

这是。在用k个元素填充堆之后，而不是在每次插入后从堆中逐出一个元素，而是在每插入k个之后从堆中逐出k个元素。然后，您不再需要堆结构-每次都选择。

关于algorithm - 是否可以从n个时间复杂度为O(n)和空间复杂度为O(k)的未排序整数中找到k个最大数？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32117950/