215. 数组中的第K个最大元素
描述
- 在未排序的数组中找到第 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 ≤ 数组的长度。
思路
- 利用STL中的优先队列构建最小堆，每次遍历与堆顶元素比较，较大则更新堆中元素，最后堆顶元素即为所求。
- 注意优先队列的定义为template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue;
- 默认为最大堆，最小堆定义为 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();
}
};
