LeetCode 0215 - Kth Largest Element in an Array

Reck Zhang

发布于 2021-08-11 12:12:22

1260

发布于 2021-08-11 12:12:22

文章被收录于专栏：Reck Zhang

Kth Largest Element in an Array

Desicription

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.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:

You may assume k is always valid, 1 ≤ k ≤ array’s length.

Solution

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        auto compare = [](int a, int b) {return a > b;};
        priority_queue<int, vector<int>, decltype(compare)> pq(compare);
        for(const auto& num : nums) {
            pq.push(num);
            while(pq.size() > k) {
                pq.pop();
            }
        }
        return pq.top();
    }
};

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

原始发表：2018-06-29，如有侵权请联系 cloudcommunity@tencent.com 删除

distinct