算法系列：寻找最大的 K 个数

http://www.cnblogs.com/noryes/

-----------------------------------------------------------------------------------------

转载自http://www.cnblogs.com/luxiaoxun/archive/2012/08/06/2624799.html

寻找N个数中最大的K个数，本质上就是寻找最大的K个数中最小的那个，也就是第K大的数。

可以使用二分搜索的策略来寻找N个数中的第K大的数。对于一个给定的数p，可以在O（N）的时间复杂度内找出所有不小于p的数。

寻找第k大的元素：

#include <iostream>using namespace std;

//快速排序的划分函数

int partition(int a[],int l,int r)

{

    int i,j,x,temp;

    i = l;

    j = r+1;

    x = a[l];

    //将>=x的元素换到左边区域

    //将<=x的元素换到右边区域

    while (1)

    {

        while(a[++i] > x);

        while(a[--j] < x);

        if(i >= j) break;

        temp = a[i];

        a[i] = a[j];

        a[j] = temp;

    }

    a[l] = a[j];

    a[j] = x;

    return j;

}

//随机划分函数

int random_partition(int a[],int l,int r)

{

    int i = l+rand()%(r-l+1);//生产随机数

    int temp = a[i];

    a[i] = a[l];

    a[l] = temp;

    return partition(a,l,r);//调用划分函数

}

//线性寻找第k大的数

int random_select(int a[],int l,int r,int k)

{

    int i,j;

    if (l == r) //递归结束

    {

        return a[l];

    }

    i = random_partition(a,l,r);//划分

    j = i-l+1;

    if(k == j) //递归结束，找到第K大的数

        return a[i];

    if(k < j)

    {

        return random_select(a,l,i-1,k);//递归调用，在前面部分查找第K大的数

    }

    else

        return random_select(a,i+1,r,k-j);//递归调用，在后面部分查找第K大的数
}

int main()

{

    int a[]={1,2,3,4,6,6,7,8,10,10};

    cout<<random_select(a,0,9,1)<<endl;

    cout<<random_select(a,0,9,5)<<endl;

    return 0;

}

如果所有N个数都是正整数，且它们的取值范围不太大，可以考虑申请空间，记录每个整数出现的次数，然后再从大到小取最大的K个。比如，所有整数都在（0, MAXN）区间中的话，利用一个数组count[MAXN]来记录每个整数出现的个数（count[i]表示整数i在所有整数中出现的个数）。只需要扫描一遍就可以得到count数组。然后，寻找第K大的元素：

for(sumCount = 0, v = MAXN-1; v >= 0; v--)

{

    sumCount += count[v];

    if(sumCount >= K)

        break;

}

return v;

极端情况下，如果N个整数各不相同，我们甚至只需要一个bit来存储这个整数是否存在（bit位为1或为0），这样使用的空间可以大大压缩。

当然也可以使用像计数排序、桶排序等这些以O(N)的时间排序算法也可以寻找第K大的数，但这也是以空间换时间为代价的。

实际情况下，并不一定保证所有元素都是正整数，且取值范围不太大。上面的方法仍然可以推广使用。如果N个数中最大的数Vmax，最小的Vmin，我们可以把这个区间[Vmax,Vmin]分成M块，每个小区间的跨度为d=(Vmax-Vmin)/M，即[Vmin,Vmin+d],[Vmin+d,Vmin+2d]......然后，扫描一遍所有元素，统计各个小区间中的元素个数，就可以知道第K大的元素在哪一个小区间。然后，再在那个小区间中找第K大的数（此时这个小区间中，第K大的数可能就是第T大的数了，这个T和每个小区间的个数有关）。我们需要找一个尽量大的M，但M的取值受到内存的限制。

解法一：该解法是大部分能想到的，也是第一想到的方法。假设数据量不大，可以先用快速排序或堆排序，他们的平均时间复杂度为O(N*logN),然后取出前K个，时间复杂度为O(K)，总的时间复杂度为O(N*logN)+O(K).
当K=1时，上面的算法的时间复杂度也是O(N*logN)，上面的算法是把整个数组都进行了排序，而原题目只要求最大的K个数，并不需要前K个数有限，也不需要后N-K个数有序。可以通过部分排序算法如选择排序和交换排序，把N个数中的前K个数排序出来，复杂度为O(N*K),选择哪一个，取决于K的大小，在K(K<logN)较小的情况下，选择部分排序。

解法二：(掌握)避免对前K个数进行排序来获取更好的性能(利用快速排序的原理)。
      假设N个数存储在数组S中，从数组中随机找一个元素X，将数组分成两部分Sa和Sb.Sa中的元素大于等于X,Sb中的元素小于X。
    出现如下两种情况：
   (1)若Sa组的个数大于或等于K，则继续在sa分组中找取最大的K个数字。
   (2)若Sa组中的数字小于K ，其个数为T，则继续在sb中找取 K-T个数字。
   一直这样递归下去，不断把问题分解成小问题，平均时间复杂度为O(N*logK)。
   代码如下：

解法三:(掌握)用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中的最小的一个。每次扫描一个数据X，如果X比堆顶元素Y小，则不需要改变原来的堆。如果X比堆顶元素大，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质。调整过程时间复杂度为O(logK)。全部的时间复杂度为O(N*logK)。
这种方法当数据量比较大的时候，比较方便。因为对所有的数据只会遍历一次，第一种方法则会多次遍历数组。如果所查找的K的数量比较大。可以考虑先求出k` ，然后再求出看k`+1 到 2 * k`之间的数据，然后一次求取。

代码如下：

解法四：这也是寻找Ｎ个数中的第Ｋ大的数算法。利用二分的方法求取TOP k问题。首先查找 max 和 min，然后计算出mid = (max + min) / 2该算法的实质是寻找最大的K个数中最小的一个。

该算法在实际应用中效果不佳。

解法五：如果N个数都是正数，取值范围不太大，可以考虑用空间换时间。申请一个包括N中最大值的MAXN大小的数组count[MAXN]，count[i]表示整数i在所有整数中的个数。这样只要扫描一遍数组，就可以得到第K大的元素。
代码如下：

        扩展问题：
1.如果需要找出N个数中最大的K个不同的浮点数呢？比如，含有10个浮点数的数组（1.5，1.5，2.5，3.5，3.5，5，0，- 1.5，3.5）中最大的3个不同的浮点数是（5，3.5，2.5）。
     解答：除了解法五不行，其他的都可以。因为最后一种需要是正数。
2. 如果是找第k到第m（0<k<=m<=n)大的数呢？
       解答：可以用小根堆来先求出m个最大的，然后从中输出k到m个。
3. 在搜索引擎中，网络上的每个网页都有“权威性”权重，如page rank。如果我们需要寻找权重最大的K个网页，而网页的权重会不断地更新，那么算法要如何变动以达到快速更新（incremental update）并及时返回权重最大的K个网页？
   解答：(解法三)用堆排序当每一个网页权重更新的时候，更新堆。

举一反三：查找最小的K个元素

解答：最直观的方法是用快速排序或堆排序先排好，在取前K小的数据。最好的办法是利用解法二和解法三的原理进行查找。

作者：阿凡卢
出处：http://www.cnblogs.com/luxiaoxun/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。