一、基本問題

題目：給定整數(shù)數(shù)組?nums?和整數(shù)?k，請返回數(shù)組中第?k?個最大的元素。

注意：你需要找的是數(shù)組排序后的第?k?個最大的元素，而不是第?k?個不同的元素。

要求：時間復雜度為 O(N)

????????看到這個問題，我們腦袋里第一個想到的就是先把整個數(shù)組排個序，然后取第 k 大就可以了。但是一看要求時間復雜度要求為 O(N) ，眾所周知，基于比較的排序的時間復雜度下限為 O(NlogN) ，不基于比較的排序又不適用于 數(shù)據(jù)范圍很大的情況，所以本題目要選擇其他思路。

????????其實只要算法題刷到一定數(shù)目，看到第 k 大和前 k 大這樣的字眼，應該條件反射出快速排序和堆排序這兩種方法，但是上述兩個排序的時間復雜度均為 O(NlogN) ，所以需要改進一下，下面給出改進方法和時間復雜度分析。

（一）快速選擇

• 算法原理

? ? ? ? 快速排序的原理就是可以一次把一個元素放到數(shù)組它對應的位置上，利用這個特性我們可以進行左右邊界的更迭達到類似二分的效果，即一次甩掉一半的元素可以不必再糾結它們的順序和大小。具體是否可以完成二分效果，取決于 base 元素的選擇，如果 base 選擇較差，那么會使算法退化到 O(N^2) 的時間復雜度；反之可以把問題規(guī)模每次都縮小一半。具體流程如下：

//快速選擇方法-迭代int findKthLargest(vector<int>& nums, int k) {int n=nums.size();int l=0,r=n-1;//初始化左右邊界while(true)//直至找到結果返回，因為一定有結果{int i=l,j=r;//相當于迭代的那個子過程int randPos=rand()%(r-l+1)+l;//隨機化尋找base元素，以免時間復雜度退化到 O(N^2)swap(nums[l],nums[randPos]);int base=nums[l];//確定base元素，為最左while(i<j){while(i<j && nums[j]<=base) j--;//選擇最左元素為base，就先遍歷右邊，注意遞增遞減順序while(i<j && nums[i]>=base) i++;if(i<j) swap(nums[i],nums[j]);}swap(nums[l],nums[i]);if(i==k-1) return nums[i];//找到第 k 大元素else if(i>k-1) r=i-1;// i 過大，更新右邊界else l=i+1;// i 過小，更新左邊界}return -1;//無實際意義，因為一定會在 while 里返回}

• 復雜度分析

? ? ? ? 上述代碼中，我們對 base 元素進行了一個隨機化選擇，這樣可以保證二分的效果，那么問題就會變成??，根據(jù)主定理時間復雜度為 O(N)。這里插一句題外話，分治問題需要判斷時間復雜度又沒什么思路的時候，可以多用下主定理。

（二）優(yōu)先隊列（堆方法）

1、利用C++的 priority_queue 數(shù)據(jù)結構

• 算法原理

? ? ? ? 建立一個小頂堆，用于存儲數(shù)組中 k 個最大的數(shù)，那么堆頂元素就是第 k 大的數(shù)。

//優(yōu)先隊列方法int findKthLargest(vector<int>& nums, int k) {priority_queue<int,vector<int>,greater<int>> tmp;//小頂堆for(int i=0;i<k;++i) tmp.push(nums[i]);for(int i=k;i<nums.size();++i){if(nums[i]>tmp.top()){tmp.pop();tmp.push(nums[i]);}}return tmp.top();}

• 復雜度分析

? ? ? ? C++中優(yōu)先隊列的 push 和 pop 都是 O(logN) 級別的，遍歷整個數(shù)組是 O(N) 級別的，故總體復雜度為 O(NlogN) 級別，哎呀，超過了題目要求。不過這種方法寫起來很簡單，思想也很容易，大家可以留作備選。

2、自建堆

? ? ? ? 面試過程中，直接用現(xiàn)成的優(yōu)先隊列，可能沒辦法滿足你的面試官，而且它的時間復雜度也沒有達標，那么只能手動撕堆了。

• 算法原理

? ? ? ? 先對數(shù)組的非葉節(jié)點進行建堆操作，然后遍歷葉子節(jié)點去跟堆頭節(jié)點交換，然后在進行堆調(diào)整，堆末元素會逐漸有序，第 k 個堆頂就是所求元素。

void adjustHeap(vector<int> &nums,int father,int heapSize)//建堆的數(shù)組，需調(diào)整的堆頭，堆大小{int left=2*father+1;int right=2*father+2;int maxPos=father;if(left<heapSize && nums[left]>nums[maxPos]) maxPos=left;if(right<heapSize && nums[right]>nums[maxPos]) maxPos=right;if(maxPos!=father){swap(nums[father],nums[maxPos]);adjustHeap(nums,maxPos,heapSize);//交換可能破壞堆性質，調(diào)整堆}}//堆排序方法int findKthLargest(vector<int>& nums, int k) {int heapSize=nums.size();for(int i=heapSize/2;i>=0;--i)//利用非葉節(jié)點建堆adjustHeap(nums,i,heapSize);for(int i=nums.size()-1;i>=nums.size()-k+1;--i)//調(diào)整 k 次，數(shù)組頭部（堆頭）為第 k 大{swap(nums[i],nums[0]);//將堆尾元素與堆頭元素交換，那么數(shù)組尾部就有序了heapSize--;//數(shù)組尾部有序，將堆 size--adjustHeap(nums,0,heapSize);//交換了頭尾元素，可能破壞堆性質，調(diào)整堆}return nums[0];}

• 復雜度分析

? ? ? ? 建堆的時間復雜度為 O(N) ，調(diào)整堆的過程中所用時間復雜度為 O(klogN) ，故總體時間復雜度為 O(N) 。? ? ? ??

二、算法推廣

題目：給定一個 int 型 的無序數(shù)組，尋找該數(shù)組的 中位數(shù)

要求：時間復雜度為 O(N)

? ? ? ? 求完了前 k 大，我相信前 k 小大家也一定可以如魚得水。那么我們再來看這個數(shù)組中位數(shù)的題目，求數(shù)組的中位數(shù)，我們一般的做法就是先把整個數(shù)組排序，然后分情況討論：當數(shù)組長度 N 為奇數(shù)時，取第??位元素為中位數(shù)；當數(shù)組長度 N 為偶數(shù)時，取第??位的平均數(shù)為中位數(shù)。但是這樣的時間復雜度還是最少為 O(NlogN)。

? ? ? ? 看完一般思路，再結合一下第 k 大問題的解決方案，是不是瞬間醍醐灌頂，本題只不過是給第 k 大問題套了個外殼。下面我僅給出偽碼，供大家參考。

double findMid(vector<int> &a) {int n=a.size();//奇數(shù)if(n%2==1) return (double)findKthLargest(a,n/2);//偶數(shù)else{int m1=findKthLargest(a,n/2-1);int m2=findKthLargest(a,n/2);return (double)(m1+m2)/2;} }

????????當然，本題也可以用最大堆（lessHeap）結合最小堆（greaterHeap）的方法來做，具體實現(xiàn)可以參考：尋找一個數(shù)組的中位數(shù)C++版本（使用priority_queue）_wxtRelax的博客-CSDN博客_queue 中位數(shù)維護一個最小堆和一個最大堆，平衡兩個堆的個數(shù)，兩種情況：最大堆比最小堆個數(shù)多 1最大堆和最小堆個數(shù)相同如果個數(shù)相等，返回兩個數(shù)的平均值。如果最大堆比最小堆個數(shù)多1，那么返回最大堆的堆頂元素即為中位數(shù)。通過下面代碼就可以實現(xiàn)：//尋找中位數(shù)double findMedian(vector<int>& data){if (data.size() == 0){return -1;}priority_queue<int, vector<ihttps://blog.csdn.net/w_weixiaotao/article/details/111999743

總結

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

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