寻找K大数的各种方法

发布时间:2016-12-10 3:28:50 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"寻找K大数的各种方法",主要涉及到寻找K大数的各种方法方面的内容,对于寻找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)    该方案快,但是其缺点在于浪费内存,对数据有要求

上一篇:Android-网络:Http下载字符串(适用网页、XML)
下一篇:信号与槽

相关文章

相关评论