广西茶叶学会 网站建设,外国人做的汉字网站,个人网站html模板下载,衡阳公司做网站给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1:
输入: [3,2,1,5,6,4], k 2…给定整数数组 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
思路一优先队列
c解法
class Solution {
public:int findKthLargest(vectorint nums, int k) {if (k 0 || k nums.size() || nums.empty()) {return 0;}priority_queueint, vectorint, greaterint que;for (int i 0; i nums.size(); i) {que.push(nums[i]);if (que.size() k1) {que.pop();}}return que.top();}
};
分析
本题要求第k大的元素利用优先队列可以不断维护排序好的数组最后直接返回第k大的元素
总结
本题考察对优先队列的利用这里采用编写好的优先队列方法将数组内数直接放入队列中进行排序
