题目描述

题目链接：215. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

例子

例子 1

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

例子 2

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

Constraints

• 1 <= k <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4

解题思路

题目要求返回数组中第 k 大的数字，可以维护一个最大尺寸的 k 的优先队列，不停压入元素，每当元素个数超过 k 时进行弹出（此时弹出的是最小元素），最后返回队列首元素即为第 k 大元素，代码如下：

#include <queue>
#include <vector>

class Solution {
public:
    int findKthLargest(std::vector<int>& nums, int k) {
        std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
        for (auto num : nums) {
            pq.push(num);
            if (pq.size() > k) {
                pq.pop();
            }
        }

        return pq.top();
    }
};

• 时间复杂度: O(nlogk)
• 空间复杂度: O(k)

GitHub 代码同步地址： 215.KthLargestElementInAnArray.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions