215. 数组中的第K个最大元素

在未排序的数组中找到第 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。