寻找K大数的各种方法

二分搜索K大数

1.?设数组中元素的个数为N，则首先对数组中的元素排序，其时间复杂度为O(NlogN)

然后从后往前数K个就行了。

其时间复杂度为O(NlogN+K)=O(NlogN)

2.?采用选择排序，O(N*K)

3.?采用快速排序的思想来处理K大数的问题，随机取出一个数字a，用a将数组分成两部分b1,b2。其中b1的数字都比a大，b2的数字都比a小。

若a的index==N-k，则返回

若a的index<N-k,则需要在b2中找第k大数即可

若a的index>N-k,则需要在b1中找第index-(n-k)个数就行了

4.?采用二分搜索求解第k大数

???过滤数组1.5N-2遍，找到数组的最大值Vmax和最小值.Vmin

??取delta，使得delta小于数组中两两元素间隔的最小值。

???对其进行二分搜索

??While(Vmax-Vmin<delta)
??{

Mid=Vmin+(Vmax-Vmin)/2;

If(FindArr(arr,N,Mid)>=k)
{//Mid偏小

Vmin=Mid;

}

Else

Vmax=Mid;

??}

二分搜索时间复杂度为O(NlogN)

5.?最小堆找k大数

???其时间复杂度为O(N*logK)

???该方案的优点在于不用一次性的将所有的数据都加载到内存中去。

6.? 利用基数排序O(N)

? ?该方案快，但是其缺点在于浪费内存，对数据有要求