Leetcode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example, Given [3,2,1,5,6,4] and k = 2, return 5.

找出无序数组中第k大的数，维护一个最小堆，使得堆的大小始终等于k，最后堆顶元素为结果。

优先队列的stl忘记了，greater是最小堆，less是最大堆，记住了！

代码语言：javascript复制

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int> > q;
        for(int i = 0; i < nums.size(); i  )
        {
            q.push(nums[i]);
            if(q.size() > k) q.pop();
        }
        return q.top();
    }
};

distinct element find return stl

0 人点赞