快捷導(dǎo)航

數(shù)組中求第K大數(shù)的實(shí)現(xiàn)方法

更新時(shí)間：2013年05月24日 16:22:00 作者：

本篇文章是對(duì)數(shù)組中求第K大數(shù)的實(shí)現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

問題：有一個(gè)大小為n的數(shù)組A[0,1,2,…,n-1]，求其中第k大的數(shù)。
該問題是一個(gè)經(jīng)典的問題，在《算法導(dǎo)論》中被作為單獨(dú)的一節(jié)提出，而且其解決方法很好的利用了分治的思想，將時(shí)間復(fù)雜度控制在了O(n)，這多少出乎我們的意料，此處暫且不表。
該問題還可以變形為：有一個(gè)大小為 n的數(shù)組A[0,1,2,…,n-1]，求其中前k大的數(shù)。
一字之差，原問題是“第k大”，變形的問題是“前k大”，但是平均時(shí)間復(fù)雜度卻都可以控制在O(n)，這不由得讓人暗暗稱奇。

我們先分析原問題：有一個(gè)大小為 n的數(shù)組A[0,1,2,…,n-1]，求其中第k大的數(shù)。
我們先取特例，令k=1，那么就是取最大的數(shù)，只要掃描一遍數(shù)組就可以確定該值，如果k=2，則掃描兩邊數(shù)組就可以確定第二大的數(shù)，依此類推下去，時(shí)間復(fù)雜度是O(k*n)，如果k跟n是一個(gè)數(shù)量級(jí)，那么時(shí)間復(fù)雜度就是O(n*n)了，顯然不是最優(yōu)的解法。

考慮分治法，難點(diǎn)在于如何將該問題分解為兩個(gè)子問題。
快速排序最基礎(chǔ)的一步：
隨機(jī)取某一個(gè)數(shù)x，將其與數(shù)組末尾元素交換，然后將比其小的數(shù)交換至前，比其大的數(shù)交換至后。
這一步使某一數(shù)組的快速排序問題分解成兩個(gè)子數(shù)組的排序問題，現(xiàn)在我們就依此來解決取第k大的數(shù)這個(gè)問題。
設(shè)數(shù)組下表從0開始，至n-1結(jié)束。
1、隨機(jī)取某個(gè)數(shù)，將其與數(shù)組末尾元素交換。
a) idx=rand(0,n-1);生成[0,n-1]間的隨機(jī)數(shù)。
b) Swap(array[idx], array[n-1]);
2、用末尾元素x，將比x小的數(shù)交換至前，比x大的數(shù)交換至后，并返回此時(shí)x在數(shù)組中的位置mid。
3、如果mid==n-k，那么返回該值，這就是第k大的數(shù)。
如果mid>n-k，那么第k大的數(shù)在左半數(shù)組，且在左半數(shù)組中是第k-(n-mid)大的數(shù)。
如果mid<n-k，那么第k大的數(shù)在右半數(shù)組，而且仍然是第k的數(shù)。

復(fù)制代碼代碼如下:

#include "iostream"
using namespace std;
int random_partion(int *p, int n)
{
     int idx=rand()%n;
     swap(p[idx], p[n-1]);
     int i=-1;    //i表示最后一個(gè)小于p[n-1]的元素的位置
     int j=0;     //j用來掃描數(shù)組
     for(j=0; j<n; j++)
     {
            //將小于p[n-1]的數(shù)交換到前半部分
            if(p[j]<p[n-1])
            {
    swap(p[++i], p[j]);
            }
     }
     swap(p[++i], p[n-1]);
     return i; 
}
int getMaxK(int *p, int n, int k)
{
 int mid;
     if(k<=0)
            return -1;
     if(n<k)
            return -1;
  mid=random_partion(p, n);   //對(duì)原數(shù)組進(jìn)行一次劃分
     if(mid == n-k)      //如果mid==n-k，那么返回該值，這就是第k大的數(shù)
   return p[mid];
     else if(mid<n-k)
   return getMaxK(p+mid+1, n-mid-1, k);  //如果mid<n-k，那么第k大的數(shù)在右半數(shù)組，而且仍然是第k大數(shù)
     else
   return getMaxK(p, mid, k-(n-mid));   //如果mid>n-k，那么第k大的數(shù)在左半數(shù)組，且在左半數(shù)組中是第k-(n-mid)大的數(shù)
}
int main(void)
{
 int num,a[] = {12012, 3, 945, 965, 66, 232, 65, 7, 8, 898, 56, 878, 170, 13, 5};
 num=getMaxK(a, 15, 4);
 printf("%d\n",num);
 system("pause");
 return 0;
}