215. 數(shù)組中的第K個最大元素

描述

• 在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 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
說明:
  你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長度。

思路

1. 利用STL中的優(yōu)先隊列構(gòu)建最小堆，每次遍歷與堆頂元素比較，較大則更新堆中元素，最后堆頂元素即為所求。
2. 注意優(yōu)先隊列的定義為template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue;
3. 默認(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();
  }
};