题目描述

未排序的数组，返回其排序后的第K个最大元素

样例

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

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

算法1

(扫描一遍 维护一个小根堆） $O(n * logk)$

遍历数组，维护一个大小为K的小根堆
为什么是小根堆，堆顶元素是堆中最小，那么还在堆中的都比它大，没在堆内的都比它小。
堆中有k个元素，那么他自然就是第K的最大元素了
找最大，用小根
值得注意的是优先队列默认的是大根堆，所以声明的时候注意参数。

时间复杂度

时间复杂度 ： 线性扫描 $O(n * logk)$
空间复杂度 ： 额外的小根堆 $O(k)$

参考文献

C++ 代码

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> q;  //小顶堆
        for(auto x : nums)
        {
            q.push(x);
            if(q.size() > k) q.pop();
        }
        return q.top();
    }
};