Leetcode 215. Kth Largest Element in an Array

triplebee

发布于 2018-01-12 14:44:38

8090

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是最大堆，记住了！

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();
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-03-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除

distinct