問題描述：

找出一個數(shù)組中第K小的元素，時間復雜度為O(n)。

解法：

1.首先大家都會想到的解法是排序，之后找出第k個元素，但是排序的時間復雜度不符合要求，或者需要額外的空間。

2.利用快排的思想，以樞紐（隨機得到）為界，將數(shù)組分為2部分，一部分小于等于這個樞紐值，一部分大于這個樞紐值，與快排不同的是，我們只處理一部分，另一部分舍棄。

代碼如下：

#include<iostream> #include<algorithm> #include<time.h> #include<cstring> #define random(x) (rand()%x) //生成隨機數(shù)用的 using namespace std; //交換兩個數(shù)的值 void swap(int arr[], int i, int j) {int tem;tem = arr[i];arr[i] = arr[j];arr[j] = tem; } int partition(int arr[], int L, int R) {int less = L - 1;int more = R;while (L < more) {if (arr[L] < arr[R]) {swap(arr, ++less, L++);}else if (arr[L] > arr[R]) {swap(arr, --more, L);}else {L++;}}swap(arr, more, R); //將樞紐從最后的位置移動到分界處int p = more;return p; //返回樞紐的位置 } int quicksort_select(int arr[], int L, int R,int k) {srand((int)time(0)); //種子，為了每次生成的隨機數(shù)不同if (k > (R - L + 1) || k < 1) {return -1;}int P;if (L < R) {swap(arr, L + (int)(random(1000) / (float)(1000)*(R - L + 1)), R); //生成一個隨機數(shù)，再把隨機數(shù)所在位置的數(shù)與數(shù)組最后一個數(shù)交換P = partition(arr, L, R);}int j = P - L + 1;if (j == k) {return arr[P];}else if (j>k) {quicksort_select(arr, L, P, k);}else {quicksort_select(arr, P + 1, R, k - j);} } int main() {//textint a[5] = { 1,2,3,4,5 };int m=quicksort_select(a, 0, 4, 2);cout << m; }

代碼分析如下：

partition函數(shù)返回樞紐的坐標P，P-L+1是左半部分元素的個數(shù)，這部分的元素都小于等于樞紐的值，右半部分的元素值都大于樞紐的值，如果j<P-L+1說明第j個小的元素，在左半部分，讓后只需要遞歸的處理左半部分即可，如果P等于j，那么很幸運，樞紐的值就是我們的所求，如果j>P-L+1，說明第k個小的元素在右半部分，指的注意的是，我們所求的數(shù)是右半部分第j-(P-L+1)小的數(shù)，我們這時候處理右半部分即可。這種方法在平均的時間復雜度是O(n)（證明看《算法導論》），但他有一個額外的產(chǎn)生隨機數(shù)，這個的效率據(jù)說很低（沒有親自探測）；

3.采用中位數(shù)線性時間選擇，我放到下一篇文章。

總結

以上是生活随笔為你收集整理的线性时间选择(TOP K)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。