這算是一道相當(dāng)經(jīng)典的算法題了：

在長度為N的亂序數(shù)組中尋找第k（n>=k）大的元素。

（1）最簡單直接的方法：先排序再找

最簡單直接的想法是首先進(jìn)行排序。假設(shè)元素的數(shù)量不大，比如才幾千個，那就可以先進(jìn)行排序，比如用快排或堆排，平均時間復(fù)雜度為O(N*logN)，然后取出前k個，于是總時間復(fù)雜度為O(NlogN)+O(k)=O(NlogN)。當(dāng)然這種做法是浪費(fèi)了不少的時間的，因?yàn)轭}目只要求找出第k大的元素，而不需要數(shù)據(jù)是有序的。

（2）比較直接的方法：部分元素排序

當(dāng)k比較小的時候，k趟排序是個比較不錯的方法。我們只需要排序最大的k個元素即可，剩下那些元素不需要管。最簡單明了的就是在冒泡排序中只進(jìn)行k趟起泡：

#include<iostream>using namespace std; int findMaxK(int a[], int n, int k) {//進(jìn)行k趟起泡即可if (k == n) k = n - 1;bool flag;for (int i = 0; i < k; i++) {flag = false;for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;if (!flag) flag = true;}}if (!flag) break;}return a[n - k]; }int main() {int A[] = { 5,1,2,2,3,4,3,10};int n=8,k =5;int result= findMaxK(A, n, k);cout << "第" << k << "大的數(shù)字為" << result << endl;system("pause");return 0; }

用上述方法，時間復(fù)雜度為O(N*k)，適用于k相對于N很小的情況。

（3）快排的分治法

快速排序使用了分治法的策略。它的基本思想是，選擇一個基準(zhǔn)數(shù)（一般稱之為樞紐元），通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分：在樞紐元左邊的所有元素都不比它大，右邊所有元素都比它大，此時樞紐元就處在它應(yīng)該在的正確位置上了。

在本問題中，假設(shè)有N個數(shù)存儲在數(shù)組a中。我們從a中隨機(jī)找出一個元素作為樞紐元，把數(shù)組分為兩部分。其中左邊元素都不比樞紐元大，右邊元素都不比樞紐元小。此時樞紐元所在的位置記為mid。

如果右半邊（包括a[mid]）的長度恰好為k，說明a[mid]就是需要的第k大元素，直接返回a[mid]。

如果右半邊（包括a[mid]）的長度大于k，說明要尋找的第k大元素就在右半邊，往右半邊尋找。

如果右半邊（包括a[mid]）的長度小于k，說明要尋找的第k大元素就在左半邊，往左半邊尋找。

// 對快排算法簡單改造了一下,返回本次的基準(zhǔn)值下標(biāo) int quickSort(int a[], int left, int right) {if (a==NULL) {return -1;}if (left>right) {return -1;}int low = left;int high = right;// 選擇基準(zhǔn)數(shù)int temp = a[left];while (low<high) {while (low<high && a[high]>=temp) {high--;}while (low<high && a[low] <= temp) {low++;}if (low<high) {int t = a[low];a[low] = a[high];a[high] = t;}}// 到這里說明low==high, 交換基準(zhǔn)數(shù)和相遇點(diǎn)的位置a[left] = a[low];a[low] = temp;return low; }int findKth(int* a, int aLen, int n, int k ) {int mid = quickSort(a, 0, aLen-1);while (mid!=aLen-k) {if (mid>aLen-k) {mid = quickSort(a, 0, mid-1);}if (mid<aLen-k){mid = quickSort(a, mid+1, aLen-1);}}return a[mid];}

時間復(fù)雜度為O(N*logk)。當(dāng)然，如果每次選擇的樞紐元素都是最壞的那個，時間復(fù)雜度就會退化為O(N*k)。

（4）借助最小堆

前面的解法都可以認(rèn)為是排序算法的變種，需要對原數(shù)組進(jìn)行多次訪問。如果原數(shù)組特別大（上百萬，甚至上億），以至于無法存放在內(nèi)存中，前面的方法就不適用了（畢竟訪問外存儲器的代價太大）。如果k足夠小（k個數(shù)據(jù)足以放入內(nèi)存），可以借助二叉堆來完成。這種解法在劍指offer中有所提及，先建立一個規(guī)模為k的最小化堆，然后每次拿待處理的數(shù)組中元素和堆的最小元素（根結(jié)點(diǎn)元素值）比較。如果待插入元素大于根結(jié)點(diǎn)元素，則在堆中刪除根結(jié)點(diǎn)，并把待處理的元素入堆。否則可以拋棄這個元素。

下面用STL標(biāo)準(zhǔn)庫中的priority_queue來模擬這個過程：

#include<iostream> #include<queue>using namespace std;struct cmp {bool operator()(int &a, int &b) const{//因?yàn)閮?yōu)先出列判定為!cmp，所以反向定義實(shí)現(xiàn)最小值優(yōu)先return a > b;} };int findMaxK(int a[], int n, int k) {priority_queue<int,vector<int>,cmp> myqueue;for (int i = 0; i < n; i++) {if (myqueue.size() < k) {myqueue.push(a[i]);}else {//將最小元素與a[i]比較int min = myqueue.top();if (a[i] > min) {myqueue.pop();}myqueue.push(a[i]);}}return myqueue.top(); }int main() {int A[] = { 1,2,2,2,3,3,3 };int n=7,k = 7;int result= findMaxK(A, n, k);cout << "第" << k << "大的數(shù)字為" << result << endl;system("pause");return 0; }

時間復(fù)雜度為O(N*logk)，因?yàn)槎娑训牟迦牒蛣h除操作都是logk的時間復(fù)雜度。

（5）鍵值索引法，桶排序

這個方法對原數(shù)組a有要求：所有 N 個數(shù)都是正整數(shù)，且它們的取值范圍不太大（假設(shè)a的所有元素都位于區(qū)間[0,max]）。此時可以申請一個規(guī)模為max+1的數(shù)組count，將count的全部元素初始化為0。然后利用count記錄a中每個元素出現(xiàn)的個數(shù)。這樣就可以在O(N)時間復(fù)雜度下找到a的第k大元素。

#include<iostream> #include<vector>using namespace std;struct cmp {bool operator()(int &a, int &b) const{//因?yàn)閮?yōu)先出列判定為!cmp，所以反向定義實(shí)現(xiàn)最小值優(yōu)先return a > b;} };int findMaxK(int a[], int n, int k,int max) {vector<int> count(max + 1);for (int i = 0; i < max; i++) {count[i] = 0;}for (int j = 0; j < n; j++) {count[a[j]]++;}int ind = max;while (k > 0) {if (count[ind] == 0) ind--;else {count[ind]--;k--;}}return ind; }int main() {int A[] = { 5,1,2,2,3,4,3,10};int n=8,k = 6;int result= findMaxK(A, n, k, 10);cout << "第" << k << "大的數(shù)字為" << result << endl;system("pause");return 0; }?

你可能會覺得，這種方法實(shí)在是好，只需O(N)的時間復(fù)雜度。但仔細(xì)想想，上面代碼實(shí)現(xiàn)的鍵值索引法并不一定是O(N)的時間復(fù)雜度。確實(shí)，一開始構(gòu)建count數(shù)組時，只需訪問原數(shù)組a一次即可，時間為O(N)，但count構(gòu)建結(jié)束后，從count中找到第k大的元素卻并不是O(N）時間。大家不妨考慮一種情況：如果max比N大得多呢？比如要找a={1,2,3,100,100}的第3大元素，首先構(gòu)建一個長度為101的數(shù)組，得把數(shù)組的全部元素置為0，O(max)。然后用count統(tǒng)計(jì)a中每個整數(shù)出現(xiàn)的次數(shù)，O(N)。最后尋找第3大元素，cout的訪問次數(shù)為接近100次。因此，這個方法實(shí)際的時間復(fù)雜度為O(max)。

結(jié)論：這種方法的時間復(fù)雜度為O(max)，當(dāng)max與N接近時，才能獲得較好的性能。若max遠(yuǎn)大于N，就是個不好的方法。

?

總結(jié)

以上是生活随笔為你收集整理的寻找数组中第k大的元素的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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