215. 數(shù)組中的第K個(gè)最大元素
描述
- 在未排序的數(shù)組中找到第 k 個(gè)最大的元素特漩。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素伶贰。
示例
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4
說(shuō)明:
你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長(zhǎng)度罐栈。
思路
- 利用STL中的優(yōu)先隊(duì)列構(gòu)建最小堆黍衙，每次遍歷與堆頂元素比較，較大則更新堆中元素荠诬，最后堆頂元素即為所求琅翻。
- 注意優(yōu)先隊(duì)列的定義為template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue;
- 默認(rèn)為最大堆，最小堆定義為 priority_queue<int, vector<int>, greater<int>> minHeap;
class Solution_215 {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (auto num : nums) {
if (minHeap.size() < k) {
minHeap.push(num);
} else if (num > minHeap.top()) {
minHeap.pop();
minHeap.push(num);
}
}
return minHeap.top();
}
};
