在一個數組中找到第k小的數（線性時間選擇）

在這一部分，我們討論的題目為元素選擇問題。這類題目的一般問法為：給定線性序集中n個元素和一個整數k，1 <= K <= n，要求找出這n個元素中第k小的元素，如（1，4，3，2，5）中第一小的元素就是1，第5小的元素就是5，第2小的元素就是2。

在某些特殊情況下，很容易設計出解選擇問題的線性時間算法。如：當要選擇最大元素或最小元素時，顯然可以在O(n)時間完成。如果k <= n/logn，通過堆排序算法可以在O(n + klogn) = O(n)時間內找出第k小元素。當k >= n - n/logn時也一樣。

一般的選擇問題，特別是中位數的選擇問題似乎比最小（大）元素要難。但實際上，從漸近階的意義上，它們是一樣的。也可以在O(n)時間完成。

?

下面我們用兩種方法進行求解。

第一種：分治算法RandomizedSelect

思想：調用了隨機劃分函數RandomizedPartition，所以這個分治算法也是一個隨機化的算法。

通過將其劃分，我們逐漸可以縮小查找的范圍進行查找。

時間復雜度：一般情況下為O(n)，最壞情況下，數字有序且找最大的數，則為O(n)

?

代碼：

#include<windows.h>#include<iostream>#include<assert.h>#include<time.h>#include<vector>#include<limits.h>using namespace std;template<class Type>int Partition(Type *ar,int left,int right){int i = left, j = right;Type tmp = ar[i];while(i<j){while(i<j && ar[j] > tmp) --j;if(i<j) { ar[i] = ar[j];}while(i<j && ar[i] <= tmp) ++i;if(i<j) { ar[j] = ar[i];}}ar[i] = tmp;return i;}template<class Type>int RandPartition(Type *ar,int left,int right){//Sleep(800);srand(time(NULL));int pos = (rand() % (right - left + 1)) + left;swap(ar[pos],ar[left]);return Partition(ar,left,right);}template<class Type>Type SelectK(Type *ar,int left,int right,int k){if(left == right && k == 1) return ar[left];int index = Partition(ar,left,right);int pos = index - left + 1;if(k <= pos) return SelectK(ar,left,index,k);else return SelectK(ar,index+1,right,k-pos);}

?

?

第二種：中位值的中位數法，類似于第一種方法，但是在最壞情況下也可以在O(n)時間內完成選擇任務的算法Select。

思想：如果能在線性時間內找到一個劃分基準，使得按這個基準所劃分出的2個子數組的長度都至少為原數組長度的ε倍(0<ε<1是某個正常數)，那么就可以在最壞情況下用O(n)時間完成選擇任務。（這里只是找到這個劃分基準（中位數的中位數）的值，而不是向快速排序那樣將這個基準值放到正確的位置上）

?

步驟：

①：將n個輸入元素劃分成n/5（向下取整）個組，每組5個元素，最多只可能有一個組不是5個元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數，共n/5（向下取整）個。

②：遞歸調用select來找出這n/5（向下取整）個元素的中位數。如果n/5（向下取整）是偶數，就找它的2個中位數中較大的一個。以這個元素作為劃分基準。

?

畫圖示意：

?

例如：按遞增順序，找出下面29個元素的第18個元素：

8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,16,5,41,7,23,22,46,29

(1) 這些元素可以分為（29）/5 == 5組（向下取整），并且排序。

分為這5組: ?(8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32),(54,16,5,41,7);

排序結果：

(2) 提取每一組的中位數元素，依次放到數組最前面并排序，構成集合{13,16,25,31,49}；

(3) 將放到最前面的各個小組的中位數傳入遞歸算法中求取中位數的中位數，得到m=25；

(4) 根據m=25, 調用快速排序，先找到值為25的數位置，再將其與第一個值進行交換，以此為基準再進行正常的快速排序，最終成功把29個元素劃分為了3個子數組（按原有順序）

• P={23,17,22,16,7,4,5,8,19,6,3,11,13}
• Q={25}
• R={43,37,57,51,32,52,49,35,60,41,54,33,31,29,46}

(5)?由于P組有13個元素,Q組有1個元素,k組有18個元素，所以我們要找的第18小元素肯定不在P組和Q組內，所以放棄P,Q，使k=18-13-1=4，對R遞歸地執行本算法；

(6)?將R劃分成3(floor(15/5))組：{31,60,33,51,57},{49,35,43,37,52},{32,54,41,46,29}

(7)?求取這3組元素的中值元素分別為：{43,49,33}，這個集合的中值元素是43;

?

(8) 根據43將R劃分成3組：?{33,37,32,31,29,35,41},{43},{52,60,49,57,51,46,54}

(9)依次這樣尋找下去，我們可以發現，幾乎每次都是對半分，接近于二分法，所以效率很高，當然這個數組中中位數沒有重復值，不過如果有，那么我們將中位數的重復值集中在中位數周圍，如果這樣的元素m >= 1，則加上一步判斷：如果j <= k <= j+m-1(j為基準前數組的個數)，則不必再進行遞歸，直接return 基準值即可，當然，這個數組中位數是沒有重復值的，所以可以很快找到第十八小元素為33。

?

時間復雜度：設數組長度為n

當n<75時，算法select所用的計算時間不超過某一常數C1，所以直接調用其他排序算法即可。

當n≥75時，for循環執行n/5次，每次用時為某一常數；select找中位數的中位數，由于長度為原長度的1/5，所以用時可記為T(n/5)；劃分以后所得到數組至多有3n/4個元素，用時記為T(3n/4)。

由此，我們得到T(n)的遞歸式為：

解此遞歸式可得T(n) = O(n)。

由于我們將每一組的大小定為5，并選取75作為是否作遞歸調用的分界點（大于75使用該算法）。這2點保證了T(n)的遞歸式中2個自變量之和n/5+3n/4=19n/20=εn，0<ε<1。這是使T(n)=O(n)的關鍵之處。當然，除了5和75之外，還有其他選擇。

?

注意：

①：設中位數的中位數是x，比x小和比x大的元素至少3*(n-5)/10個，原因：3*(n/5-1)*1/2

• 3---中位數比x小的每一組中有3個元素比x小
• n/5-1---有5個數的組數
• 1/2---大概有1/2組的中位數比x小

②：而當n≥75時，3(n-5)/10≥n/4所以按此基準劃分所得的2個子數組的長度都至少縮短1/4，也就是說，長度最長為原長度的3/4。

如圖，劃分的左上部分肯定是要比x小的（大概占1/4）右下部分是肯定比x大的（大概占1/4）左下和右上不確定，就算這兩部分同時不比x小或比x大，在極端情況下劃分成的子區間也能至少縮短1/4!

?

代碼：

#include<iostream>#include<cstdio>#include<cstring>#include<stack>#include<algorithm>using namespace std;void bubbleSort(int a[],int p,int r){for(int i=p;i<r;i++){for(int j=i+1;j<=r;j++){if(a[j]<a[i])swap(a[i],a[j]);}}}int Partition(int a[],int p,int r,int val){int pos;for(int q=p;q<=r;q++){if(a[q]==val){pos=q;break;}}swap(a[p],a[pos]);int i = p, j = r;int tmp = ar[i];while(i<j){while(i<j && ar[j] > tmp) --j;if(i<j) { ar[i] = ar[j];}while(i<j && ar[i] <= tmp) ++i;if(i<j) { ar[j] = ar[i];}}ar[i] = tmp;return i;}int Select(int a[],int p,int r,int k){if(r-p<75){bubbleSort(a,p,r);return a[p+k-1];}for(int i=0;i<=(r-p-4)/5;i++){//把每個組的中位數交換到區間[p,p+(r-p-4)/4]int s=p+5*i,t=s+4;for(int j=0;j<3;j++){//冒泡排序，從后開始排，結果使得后三個數是排好順序的（遞增）for(int n=s;n<t-j;n++){if(a[n]>a[n+1])swap(a[n],a[n-1]);}}swap(a[p+1],a[s+2]);//交換每組中的中位數到前面}//(r-p-4)/5表示組數-1，則[p,p+(r-p-4)/5]的區間長度等于組數int x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);//求中位數的中位數int i=Partition(a,p,r,x),j=i-p+1;if(k<=j)return Select(a,p,i,k);else return Select(a,i+1,r,k-j);}

?

參考博客：https://blog.csdn.net/m0_37579232/article/details/80178000

?

總結

以上是生活随笔為你收集整理的在一个数组中找到第k小的数（线性时间选择）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。