題目

在未排序的數組中找到第 k 個最大的元素。請注意，你需要找的是數組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2 輸出: 5
示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4 輸出: 4
說明:
你可以假設 k 總是有效的，且 1 ≤ k ≤ 數組的長度。

來源：力扣（LeetCode）
鏈接：Leetcode215 數組中第k大的數

思路

使用最小堆。最小堆的堆頂元素是最小的。
所以我們要維護的是前k大元素的一個最小堆，這樣，堆頂就是我們要找的第k大的數。

時間復雜度是nlogK ,這里K是所維護的堆的大小
當n很大時，nlogK會比 n*logn 小很多。

代碼

class Solution { public:int findKthLargest(vector<int>& nums, int k) {priority_queue <int,vector<int> ,greater<int> > Q;//構建最小堆for(size_t i=0;i<nums.size();++i)//遍歷數組{if(i<k)//堆中元素小于k個，則裝滿堆Q.push(nums[i]);else if(nums[i]>Q.top()&&!Q.empty())//比堆頂元素大的入堆{Q.pop();Q.push(nums[i]);}}return Q.top();//返回最小堆的堆頂元素} };

堆的復習

下面是堆的簡單語法:

二叉堆，即優先級隊列 priority_queue,在頭文件queue中
最小堆：最小值先出的完全二叉樹。
最大堆：最大值先出的完全二叉樹。

假定big_heap 為一個堆
big_heap.empty()//判斷堆是否為空，如果為空返回真
big_heap.pop()//彈出堆頂元素
big_heap.push(x)//將元素x入堆
big_heap.top()//得到堆頂元素
big_heap.size()//得到堆的大小

#include<iostream> #include<queue> using namespace std; int main() {priority_queue<int> big_heap;//默認構造最大堆 priority_queue< int,std::vector<int>,std::greater<int> > small_heap;//構造最小堆 priority_queue <int, std:: vector<int>,std::less<int> > big_heap2;//構造最大堆 if (big_heap.empty())cout<<"the big_heap is empty"<<endl;int test[]={1,2,5, 66,2,4};for(size_t i=0;i<6;++i){big_heap.push(test[i]);//入堆 }cout<<"the maximum is "<<big_heap.top()<<endl; //堆頂元素 big_heap.push(1000);cout<<big_heap.top()<<endl;cout<<"the size: "<< big_heap.size()<<endl;//堆的大小 }

堆的練習結果：

希望對你有幫助。

總結

以上是生活随笔為你收集整理的Leetcode215数组中第k大的数-最小堆的全部內容，希望文章能夠幫你解決所遇到的問題。

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