【编程之美】2.5 寻找最大的k个数

有若干个互不相等的无序的数，怎么选出其中最大的k个数。

我自己的方案：因为学过找第k大数的O(N)算法，所以第一反应就是找第K大的数。然后把所有大于等于第k大的数取出来。

写这个知道算法的代码都花了2个多小时，反思，太慢了。 注意边界条件，不要混混沌沌的。

/************我自己的解法*****************/

//选择数组a[N]中最大的第k个数

int Select(int * a, int N, int k)

{

    if(k > N || a == NULL)

    {

        cout << "error!!!";

    }

    if(N < )

    {

        qsort(a, N, sizeof(a[]), cmp);

        return a[N - k];

    }

    int arrNum = N/; //可以整除5的数字

    int surplus = N % ; //除以5剩下的数字

    int * mid = new int [arrNum]; //存储每一组的中位数

    int * S1 = new int [N];

    int * S2 = new int [N];

    int posS1 = ;

    int posS2 = ;

    for(int i = ; i < arrNum; i++)

    {

        qsort(a+i*, , sizeof(a[]), cmp);

        mid[i] = *(a + i *  + );

    }

    int midNum = Select(mid, arrNum, arrNum/);

    for(int i = ; i < arrNum; i++)

    {

        int * currentGroup = a + i * ;

        if(currentGroup[] < midNum)

        {

            memcpy(S1 + posS1, currentGroup,  * sizeof(a[]));

            posS1 += ;

            for(int j = ; j < ; j++)

            {

                if(currentGroup[j] <= midNum)

                    S1[posS1++] = currentGroup[j];

                else

                    S2[posS2++] = currentGroup[j];

            }

        }

        else

        {

            memcpy(S2 + posS2, currentGroup + ,  * sizeof(a[]));

            posS2 += ;

            for(int j = ; j < ; j++)

            {

                if(currentGroup[j] <= midNum)

                    S1[posS1++] = currentGroup[j];

                else

                    S2[posS2++] = currentGroup[j];

            }

        }

    }

    for(int i = arrNum * ; i < N; i++)

    {

        if(a[i] <= midNum)

            S1[posS1++] = a[i];

        else

            S2[posS2++] = a[i];

    }

    if(k == posS2)

    {

        return midNum;

    }

    else if(k < posS2)

    {

        return Select(S2, posS2, k);

    }

    else

    {

        return Select(S1, posS1, k - posS2);

    }

}

int * GetBiggestK(int * a, int N, int k)

{

    int * biggestK = new int [k];

    int numK = Select(a, N, k);

    int pos = ;

    for(int i = ; i < N; i++)

    {

        if(a[i]>=numK)

        {

            biggestK[pos++] = a[i];

        }

    }

    return biggestK;

}

编程之美对这种算法的评价是：由于这个线性算法的常数项比较大，在实际应用中有时效果并不好。

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

书上的解法：

解法一： 先排序，再取出最大的k个数 复杂度 O(NlogN)

解法二：类似于快速排序，先在数据中选一个数做标准，把数据划分为两个部分，大于等于选中数字S1个 和 小于选中数字S2个 。如果S1大于k则在S1个数中继续找最大的k个，如果S1小于k,则把这S1个数加入答案，并在S2中继续找其他的数字。 平均复杂度为O(NlogK).

/*********答案中 解法二*****************/

int * GetBiggestKAns2(int * a, int N, int k)

{

    if(a == NULL || k > N)

    {

        cout << "error!!!"<< endl;

        return NULL;

    }

    int first = a[];

    int head = ;

    int tail = N - ;

    int numAlready = ;

    int postion = GetPosition(a, first, head, tail);

    swap(a[], a[postion]);

    if(postion +  == k)

    {

        int * ans = new int [k];

        memcpy(ans, a, k * sizeof(a[]));

        return ans;

    }

    else if(postion +  > k)

    {

        return GetBiggestKAns2(a, postion + , k);

    }

    else

    {

        int * ans = new int [k];

        memcpy(ans, a , (postion + ) * sizeof(a[]));

        int * ansPart = GetBiggestKAns2(a + postion + , N - postion - , k - postion - );

        memcpy(ans + postion + , ansPart, (k - postion - ) * sizeof(a[]));

        return ans;

    }

}

//交换时让大数在前，小数在后

int GetPosition(int * a, int first, int p, int r)

{

    int head = p;

    int tail = r;

    while(head < tail)

    {

        while(a[head] >= first)

            head++;

        while(a[tail] < first)

            tail--;

        if(head < tail)

        {

            swap(a[head], a[tail]);

            head++;

            tail--;

        }

    }

    return head - ; //如果所有的数字都比first大 那么head会指向数组后的第一个数字

                     //如果所有的数字都比first小 那么head会指向第一个数字 都是恰好head - 1 是应该交换的位置

}

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

解法三：用二分法找第k大的数 数据分布平均情况下，时间复杂度为O(NlogN)

伪代码如下：

while(Vmax - Vmin > delta)

{

   Vmid = Vmin + (Vmax - Vmin) * 0.5;

   if(f(arr, N, Vmid) >= K)

   {

        Vmin = Vmid;

   }

   else

   {

        Vmax = Vmid;

   }

}    

f(arr, N, Vmid) 返回数组arr[0...N-1]中大于等于Vmid的数的个数。delta是比数组中数字的最小差值还要小的数。

最后[Vmid, Vmax]只剩下一个数，就是第k大的数。

另一个思路：若所有的数都是整数，可以比较他们的二进制位，从最高位开始，1的是较大的数 有A个，0的是较小的数有B个。若 A > K则在A中找最大的K个，反之 把A个数加入答案， 在B中找 最大的K - A个数。

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

解法四：用一个最小堆存储最大的那K个数，先把K个数加入最小堆，新来一个数就与最小堆的根节点对比，比根节点小丢弃，比根节点大则替换根节点，调整最小堆。这样遍历完后最小堆里的数字就是最大的K个数。 时间O(NlogK)

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

解法五：若数字的范围是有限的整数，可以分配一个count[MAXN]的数组，count[0]记录0在数组中出现的次数...这样只要遍历一遍数组得到count再遍历一遍count就可以找到最大的K个数了。

【编程之美】2.5 寻找最大的k个数的相关教程结束。