鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

N个整数寻找k个最小的数

来源:互联网 作者:佚名 时间:2015-09-25 05:46
找出第k大的数字 利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分S a 和S b 。S a 中的元素大于等于X,S b 中元素小于X。这时有两种情况: 1. S a 中元素的个数小于k,则S b 中的第k-|S a |个元素即为第k大数; 2. S a 中元素的个数大于

找出第k大的数字

利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。这时有两种情况: 
1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数; 
2. Sa中元素的个数大于等于k,则返回Sa中的第k大数。时间复杂度近似为O(n)

找出前K大数:

思路:快速排序。主要思想是找一个“轴”节点,将数列交换变成两部分,一部分全都小于等于“轴”,另一部分全都大于等于“轴”,然后对两部分 递归处理。其平均时间复杂度是O(NlogN)。从中可以受到启发,如果我们选择的轴使得交换完的“较大”那一部分的数的个数j正好是n,不也就完成了在 N个数中寻找n个最大的数的任务吗?当然,轴也许不能选得这么恰好。可以这么分析,如果j>n,则最大的n个数肯定在这j个数中,则问题变成在这j 个数中找出n个最大的数;否则如果j<n,则这j个数肯定是n个最大的数的一部分,而剩下的j-n个数在小于等于轴的那一部分中,同样可递归处理。
这个算法的平均复杂度是O(N)的。 


转自http://blog.sina.com.cn/s/blog_5b101dbf0100o82b.html 

网友评论
<