215. 数组中的第K个最大元素
难度中等1787
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
代码语言：javascript复制输入: [3,2,1,5,6,4], k = 2
输出: 5示例 2:
代码语言：javascript复制输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
这道题有多种解法
思路一：
先将这个数组进行排序，然后返回第k大的元素下标即可。
代码语言：javascript复制//第一种写法
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};
//第二种写法
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.rbegin(), nums.rend());
return nums[k - 1];
}
};
//第三种写法
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), greater<int>());
return nums[k - 1];
}
};思路二：
运用优先级队列，将数组的元素放到优先级队列中排序，默认为大堆，然后进行 k - 1次的 pop 掉队头的位置，最后第 k 个大的数字就在对头的位置了！
代码语言：javascript复制class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//将数组里面的数据先放到优先级队列中，默认为大堆
priority_queue<int> p(nums.begin(), nums.end());
//将队列中前k-1个最大的元素pop掉
for(int i = 0; i < k - 1; i)
{
p.pop();
}
return p.top();
}
};时间复杂度：O(K K*logN)
时间复杂度：O(N)
所以当这个数组很大的时候，可能会导致内存不够，所以可以看下面这种最优的解放。
思路三（最优解法）：
与思路二不同，这次我们用优先级队列存储 k 个数，而且是按小堆存放！
然后让数组里面剩余元素依次与对头比较，若比对头还大的话，则入堆，反之则跳过，依次循环，直到数组遍历完成。
代码语言：javascript复制class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//创建k个空间的小堆
priority_queue<int, vector<int>, greater<int>> p(nums.begin(), nums.begin() k);
//将每次大于堆顶的数据入堆
for(size_t i = k; i < nums.size(); i)
{
if(nums[i] > p.top())
{
p.pop();
p.push(nums[i]);
}
}
return p.top();
}
};这种解法当K很大的时候的时间复杂度与思路二差不多：*O(K (N - K)logK)
但是对于空间复杂度的优化则非常的大：O(K)
