在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
本题可以采用优先队列的数据结构，这样的话答案是比较简单就能解答出来的，只需要当优先队列里的值大于k就删掉顶部的就可以了，最后返回优先队列中的顶部的数据就是答案。
以 3,2,1,5,6,4 k=2为例子
3加入优先队列，优先队列大小为1，不做处理。此时优先队列：3
2加入优先队列，优先队列大小为2，不做处理。此时优先队列: 2,3
1加入优先队列，优先队列大小为3，此时优先队列为：1,2,3 删去顶部的1
5加入优先队列，优先队列大小为3，此时优先队列为2,3,5，删去顶部的2
6加入优先队列，优先队列大小为3，此时优先队列为3,5,6，删去顶部的3
4加入优先队列，优先队列大小为3，此时优先队列为4,5,6，删去顶部的4
最后返回5即是答案。
代码如下：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int,vector<int>,greater<int>> myQueue;
for(int n : nums){
myQueue.push(n);
if(myQueue.size()>k) myQueue.pop();
}
return myQueue.top();
}
};
上面一种方法是用了已有的数据结构，还可以用快排的思想去解决这道题。
第 k 个最大的元素,其实就是第 N-k个最小元素。
其实就是快排序号N-k的元素了，而且这道题做起来比快排要快，因为你每次切分数组得到的序号和k做比较，只要搜索一半即可。如果切分得到的序号比k大，那么显然这个答案在前一块切分数组当中，那就不需要排序后面的数组了。因此快排的平均时间复杂度只需要O(N),是比之前的O(N*logk)要高的。
代码如下：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n=nums.size();
return quickSort(nums,0,n-1,n-k);
}
int partition(vector<int>& nums,int left,int right){
int i=left,j=right+1;
int v=nums[left];
while(true){
while(v>nums[++i]) if(i == right) break;
while(v<nums[--j]) if(i == left) break;
if(i >= j) break;
exch(nums,i,j);
}
exch(nums,left,j);
return j;
}
int quickSort(vector<int>& nums,int left,int right,int k){
if( left == right )
return nums[left];
int j=partition(nums,left,right);
if(j == k){
return nums[j];
}
if(j>k){
return quickSort(nums,left,j-1,k);
}
else{
return quickSort(nums,j+1,right,k);
}
}
void exch(vector<int>& nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
};
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
网友评论