在一个包含N个元素的整数数组中，找到最小k个元素?(复制)

Possible Duplicate:
Worst-case O(n) algorithm for doing k-selection

可能重复:最坏情况O(n)算法进行k-选择

Given the following question :

有以下问题:

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

You can assume that N is a large number.

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

I'm thinking about a minimum heap , anyone has a better solution ?

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

Regards

问候

3 个解决方案

#1

If K << N, min heap is good enough because creation of heap is O(n), and if K << N selecting first K items is at most O(N), otherwise you could use selection algorithm to find Kth smallest element in O(n) then select numbers which are smaller than found item. (Sure if some numbers are equal to Kth element select till fill K items).

如果K << N，最小堆足够好，因为堆的创建是O(N)，如果K << N选择第一个K项最多是O(N)，那么可以使用选择算法找到O(N)中第K个最小的元素，然后选择小于发现项的数字。(如果某些数字等于第K个元素，请选择直到填满K个项目)。

#2

What about this:

这个:

Sort the array (quicksort or heapsort are great for integer arrays), and iterate to k

对数组进行排序(快速排序或heapsort对于整数数组来说很好)，并迭代到k

#3

I think you can do this one in O(N*log(K)). Pseudocode:

我认为你可以用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

Requires:

要求:

N list removals from end (N * O(1))
N从端清除列表(N * O(1))
at most N sort-maintaining list inserts (N * O(log(listsize)))
最多N次保持列表插入(N * O(log(列表大小)))

list's size is bounded by K

列表的大小以K为界

Thus, O(N * log(K)) time.

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

#1

#2