letcode::数组中的第k个最大元素

数组中的第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

思路：

sort排序 从大到小排序后，返回第k-1个元素。优先队列 大堆的时间复杂度是 k ∗ l o g 2 N k * log_2N k∗log2​N 小堆的时间复杂度是 ( N − K ) ∗ l o g 2 K (N-K)*log_2K (N−K)∗log2​K 当k不大时，还是与O(N)接近的。

代码：

sort排序

class Solution { public: int findKthLargest(vector<int>& nums, int k) { sort(nums.begin(), nums.end(), greater<int>()); return nums[k - 1]; } };

大堆

class Solution { public: int findKthLargest(vector<int>& nums, int k) { //大堆 k * logN priority_queue<int> pq(nums.begin(), nums.end()); while (--k) { pq.pop(); } return pq.top(); } };

小堆

class Solution { public: int findKthLargest(vector<int>& nums, int k) { //小堆 （N- K）* logN priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k); for (int i = k; i < nums.size(); ++i) { if (nums[i] > pq.top()) { pq.pop(); pq.push(nums[i]); } } return pq.top(); } };