2.5 寻找最大的K个数

题目：有很多无序的数，怎么选出最大的K个数？

 

解法1：最简单、最直接--排序！没什么闪光点，而且数目规模大的话，数组装不下，编译不了。

 

解法2：转化为寻找第K大的数（参考《算法设计与分析》中的线性选择算法），然后遍历。

 

解法3：二分答案。设数组中最大的数为vmax，最小的数为vmin。那么，第K大的数必然在[vmin,vmax]中，不断二分这个区间的数值寻找答案。

时间复杂度达到O(nlogn)，当做拓展思路吧。

 

while(r-l>bound)  //可能是浮点数，边界bound是比任意2个数之差还要小的数。
{
    mid=(l+r)/2;
    if(calc(a,n,mid)>=k) //calc()函数返回数组中不小于mid的元素个数 
        l=mid;
    else
        r=mid;                    
}

 

以上解法，都是假定在数据规模比较少的条件下。若有10^8个数时，数组无法直接储存，编译不了。

---

解法4：堆排序。建立只有K个元素的小顶堆，堆顶元素a[0]最小。遍历所有的数，若发现a[x]>a[0]，则a[0]=a[x]，然后调整堆。本方法顺利地解决了空间问题。时间复杂度为O(nlogn)

 

if(x>a[0])
{
    a[0]=x;
    p=0;
    while(p<k)
    {
        q=p<<1+1;
        if(q>=k)  //a[]是从0开始的 
            break;
        if(q+1<k&&a[q]>a[q+1]) 
            q++;        //q指向左右两子树中最小的一个 
        if(a[p]>a[q])
        {
            int t=a[p];
            a[p]=a[q];
            a[q]=t;
            p=q;             
        }       
        else
            break;   
    }          
} 

解法5：这个比较有意思。用count[n]数组记录数字n出现的次数，遍历一遍，即可求第K大的数。实现很简单，但是缺点很明显。数据规模不能太大，而且必须为整型。

 

附书中代码：

for(sumcount=0,v=maxn-1;v>=0;v--)
{
    sumcount+=count[v];
    if(sumcount>=k)
        break;                                 
}
return v;