arrays - 在具有 N 个元素的整数数组中，找到最小的 k 个元素？

Question

可能重复：
用于进行 k 选择的最坏情况 O(n) 算法

鉴于以下问题：

In an integer array with N elements , find the minimum k elements (k << N)

你可以假设这N是一个很大的数字。

我正在考虑最小堆，有人有更好的解决方案吗？

问候

Answer 1

如果 K << N，min heap 就足够了，因为创建堆是 O(n)，如果 K << N 选择前 K 个项目最多 O(N)，否则你可以使用选择算法找到第 K 个最小元素O(n)然后选择小于找到的项目的数字。（确定如果某些数字等于第 K 个元素，则选择直到填充K项目）。

Answer 2

那这个呢：

对数组进行排序（快速排序或堆排序非常适合整数数组），然后迭代到 k

Answer 3

我认为你可以在 O(N*log(K)) 中做到这一点。伪代码：

haz array[N]
haz output[k] (itz a list)

i iteratez on array with array[N] az element:
    i insertz element into output (i maintainz strict ordering)
    i removez largest element of output when output size iz bigger than k

要求：

• 从末尾删除 N 个列表 (N * O(1))
• 最多 N 次排序维护列表插入 (N * O(log(listsize)))

列表的大小以 K 为界

因此，O(N * log(K)) 时间。