LeetCodeDay57 —— 数组中的第K个最大元素★☆

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 ≤ 数组的长度。

思路

1. 利用STL中的优先队列构建最小堆，每次遍历与堆顶元素比较，较大则更新堆中元素，最后堆顶元素即为所求。
2. 注意优先队列的定义为template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue;
3. 默认为最大堆，最小堆定义为 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();
  }
};