题目描述
题目链接:215. Kth Largest Element in an Array
Given an integer array nums and an integer
k
, return thekth
largest element in the array.Note that it is the
kth
largest element in the sorted order, not thekth
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