【LeetCode】【数组中的第K个最大元素】
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示:
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这里我们可以直接构建一个大根堆,然后pop K-1次,得到第K大的数
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//用迭代器区间去构造
//相当于是一个建大堆的过程--O(N)
//如果N非常大的话,可以键一个k个数的小堆
priority_queue<int> maxHeap(nums.begin(),nums.end());
//O(logN*k)
while(--k)
{
maxHeap.pop();
}
return maxHeap.top();
}
};