网站简单设计,中南路网站建设公司,业之峰家装公司地址,wordpress 多站点开启leetcode原题链接#xff1a;数组中的第K个最大元素
题目描述 给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O… leetcode原题链接数组中的第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
解题方法 小顶堆。求最大的k个元素用小顶堆求最小的k个元素用大顶堆。同时注意下c的语法糖。std::less用于定义大顶堆, std::greater用于定义小顶堆。
C代码
#include iostream
#include vector
#include queue
#include functional // std::less, std::greater
/*
* 最大的k个元素采用小顶堆, std::greater
* 最小的k个元素采用大顶堆, std::less
* std::priority_queue的成员函数如下:
* empty(),size(),top(),push(), emplace()[c11], pop(), swap(c11)
*/class Solution {
public:int findKthLargest(std::vectorint nums, int k) {int n nums.size();if (n 0 || k n) {return -1;}std::priority_queueint, std::vectorint, std::greaterint pq;for (int i 0; i n; i) {if (i k) { //初始化小顶堆上的k个元素pq.emplace(nums[i]);} else if (nums[i] pq.top()) { //当前遍历的数字比堆顶元素大pq.pop();//先弹出堆顶元素pq.emplace(nums[i]);//再压入元素}}return pq.top();//小顶堆的头节点就是第k大元素}
};
