题解 | 寻找第K大

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param n int整型 
     * @param K int整型 
     * @return int整型
     */
    int findKth(vector<int>& a, int n, int K) {
        // write code here
        if(K==0||K>n)
        {
            return -1;
        }
        priority_queue<int, vector<int>, greater<int>> pq;//最小堆
        //最小堆，k个数的堆里最小的那个就是这k个数中第k大的数
        //假设前k个数为最大的k个数，最小堆的top是这k个数里最小的那个数
        //如果最小堆的top比第k+1个数还要大，那么这k个数就是迄今为止见过的
        //最大的k个数，如果比top还要小，那么就让top出去，让这个数进来，此时
        //最小堆里的k个数就是迄今为止见过的最大的k个数，以此类推，直到结束
        for(auto i:a)
        {
            if(pq.size()<K)
            {
              pq.push(i);
            }
            else 
            {
                if(pq.top()<i)
                {
                    pq.pop();
                    pq.push(i);
                }
            }
        }
        if(!pq.empty())
        {
            return pq.top();
        }
        return -1;
    }
};