在n个项的数组中找到k个最小数的算法

Question

我正在尝试编写一种算法,该算法可以在O(n)时间内打印n个大小数组中的k个最小数字,但我无法将时间复杂度降低到n.我怎样才能做到这一点？

Answer 1

我之前在接受采访时已经这样做了,其中一种最优雅/最有效的方法就是这样做

O(n log k). 
with space: O(k) (thanks, @Nzbuu)

基本上你将使用大小限制为k的最大堆.对于数组中的每个项目,检查它是否小于最大值(仅O(1)).如果是,则将其放入堆中(O(log k))并删除最大值.如果它更大,请转到下一个项目.

当然,堆不会产生k个项的排序列表,但这可以在O(k log k)中完成,这很容易.

类似地,您可以执行相同的操作来查找最大的k项,在这种情况下,您将使用最小堆.

Answer 2

你需要使用'选择算法'找到第k个最小元素,即O(n),然后再次迭代数组并返回每个小于/等于它的元素.
选择算法:http ://en.wikipedia.org/wiki/Selection_algorithm
如果你有重复,你将不得不注意:你需要确保你没有返回更多的k元素(例如你有可能1,2,...,k,k,k,...)

编辑:
完整算法,并按要求返回一个列表:让数组为A

 1. find the k'th element in A using 'selection algorithm', let it be 'z'
 2. initialize an empty list 'L'
 3. initialize counter<-0
 4. for each element in A: 
 4.1. if element < z: 
   4.1.1. counter<-counter + 1 ; L.add(element)
 5. for each element in A:
 5.1. if element == z AND count < k:
   5.1.1. counter<-counter + 1 ; L.add(element)
 6. return L

请注意,如果列表可能有重复项,则需要进行第3次迭代.如果它不能 - 它是不必要的,只需将4.1中的条件更改为<=.
还要注意:L.add正在向链表中插入一个元素,因此是O(1).

Answer 3

假设您正在尝试显示K个最小数字,您可以使用Hoare选择算法来查找第k ^个最小数字.将数组划分为较小的数字,第k ^个数字和较大的数字.

Answer 4

只需使用归并排序对数组进行排序，然后打印前 k 个数字，在最坏的情况下将需要 n*log2(n) 。