第k小整數問題

問題描述

有 n 個正整數，要求出這 n 個正整數中的第 k 個最小整數。

思路一：桶排序

//桶排序
void tong(int n, int k, int *a, int *res){
    for(int i=1;i<=n;i++){
        res[a[i]]++;
    }
    int ct=0;
    for(int i=1;i<30010;i++){
        if(res[i]){
            ct++;
        }
        if(ct==k){
            cout<<i;
            break;
        }
    }
}
           

桶排序實作起來比較簡單。

思路二：分治法

//分治法
//left：快排的最左側下标
//right：快排的最右側下标
//n：數組内資料總數
//k：目标要找的第k大
//a：數組
void qs(int left ,int right, int n, int k, int *a){
    //m：作為參照的中間值的下标
    //middle：作為參照的中間值
    int l=left, r=right, m=(l+r)/2;
    int middle=a[m];
    int i=l, j=r;
    while(i<=j){
        if(a[i]>middle)
            i++;
        if(a[j]<middle)
            j++;
        if(i<=j){
            int tmp=a[i];
            a[i]=a[j];
            a[j]=tmp;
            //當中間值換了位置 要換m下标值
            if(i==m)
                m=j;
            if(j==m)
                m=i;
        }
    }
    if(m==k)//說明第k小數就是middle
        cout>>middle;
    if(m>k)//說明第k小數在左邊
        f2(1, k-1, k-1, k, a);
    if(m<k)//說明第k小數在右邊
        f2(K+1, n, n-k, k, a);

}
           

主要利用部分快排的思想，選一個參照值（我這裡每次取的是位于數組中間的那個值），進行一次快排，将數組大緻分為

（比參照值小的，參照值，比參照值大的）

這三組。

然後按照m與k的大小關系分類，m>k時顯然要找的數在middle值的左邊，是以接下來隻用讨論middle值左邊的那組資料；m<k時顯然就隻用讨論middle值右邊的那組資料。

需要注意的是需要記錄middle值的下标，因為當middle值與其他值進行交換操作時，它的下标也應該換成交換後所處位置的下标。比如：

初始時中間值middle為20，下标是5（數組從1開始存放）。經過一次快排後20被放到了最後，m應變為9。