天天看點

leetcode-215 數組中的第K個最大元素

在未排序的數組中找到第 k 個最大的元素。請注意,你需要找的是數組排序後的第 k 個最大的元素,而不是第 k 個不同的元素。

示例 1:

輸入: [3,2,1,5,6,4] 和 k = 2

輸出: 5

int findKthLargest(vector<int>& nums, int k) {
    //C++使用優先級隊列實作堆
    //如果是greater<int>,則最小堆
    //如果是less<int>,則最大堆
    priority_queue<int , vector<int>, greater<int>> Q;
    for (int i = 0;i < nums.size(); ++i) {
        if(k > 0) {
            Q.push(nums[i]);
            k--;
        } else {
            if (nums[i] > Q.top()) {
                Q.pop();
                Q.push(nums[i]);
            }
        }
    }
    return Q.top();
}