我知道我们可以通过两种方式从 n 个未排序的整数中找到 k 大的数:
- 使用quick-select之类的算法找到第K大的数,然后我们就可以得到第k大的数。时间复杂度O(n),空间复杂度O(n)
- 使用堆来存储 k-最大的数字并迭代 n 个整数,然后将适当的整数添加到堆中。时间复杂度O(nlogk),空间复杂度O(k)
假设 n 个整数在一个流中,我们不能随机访问它们
我想知道是否有可能从时间复杂度 O(n) 和空间复杂度 O(k) 的 n 个未排序的整数中找到 k 个最大的数?
最佳答案
是的。用 k 个元素填充堆后,不是在每次插入后从堆中逐出一个元素,而是在每 k 次插入后从堆中逐出 k 个元素。然后您不再需要堆结构——只需每次选择即可。
关于algorithm - 是否有可能从 n 个未排序的整数中找到时间复杂度 O(n) 和空间复杂度 O(k) 的 k 个最大数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32117950/