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

思路一：优先队列（小根堆）

【c++】STL里的priority_queue用法总结_小拳头的博客-CSDN博客_priority_queue头文件

priority_queue,greater> p;

优先队列默认为大根堆，priority_queue p等于priority_queue,less> p

时间复杂度：小根堆的插入删除时间复杂度为O(logN)，for循环遍历整个数组，所以时间复杂度为O(NlogN)，是不满足题意O(N)，不过可以提交通过。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        priority_queue<int,vector<int>,greater<int>> p;
        for(int i=0;isize();i++)//所有元素都进一次小根堆
        {
            p.push(nums[i]);
            if(i>=k)//如果元素个数大于等于k，就把小根堆的堆顶元素（最小值）出出去
            {
                p.pop();
            }
        }
        int res=p.top();//此时小根堆有k个元素，堆顶的元素就是第k个最大的元素
        return res;
    }
};

思路二：快速选择算法（循环，不是递归）

快速选择算法是快速排序的变体。第 k 个最大的元素，相当于数组升序排序的下标为 n - k 的元素（第n-k+1个元素）。

在快速排序算法 partition 函数执行时，会将 nums[p] 排到正确的位置，使得 nums[low..p-1] < nums[p] < nums[p+1..high]，此时就知道 nums[p] 的排名了。

那么我们可以把 p 和 n-k 进行比较，如果 p < n-k 说明要找的元素在 nums[p+1..high] 中，如果 p > n-k 说明要找的元素在 nums[low..p-1] 中。

然后，去 nums[p+1..high] 或者 nums[lo..p-1] 这两个子数组中执行 partition 函数，就可以进一步缩小范围，最终找到目标元素。

时间复杂度：O(N)，不断循环，缩小范围，找到第k个最大的元素。

class Solution 
{
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(NULL));//设置随机种子
        random_shuffle(nums.begin(),nums.end());//使用random_shuffle需要先设置随机种子
        int n = nums.size();
        int low = 0;
        int high = n - 1;
        while (low<=high)//不断缩小范围
        {
            int p = partition(nums,low,high);
            if (p == n-k)
                return nums[p];
            else if (p < n-k)
                low = p + 1;
            else    
                high = p - 1;
        }
        return -1;
    }
 
    //----左右交换
    int partition(vector<int> & nums, int low, int high)//同快速排序的partition函数
    {
        int pivot = nums[low];
        int i=low+1;
        int j=high;
        while (i<=j)
        {
            while(i
                i++;
            while(j>low&&nums[j]>=pivot)
                j--;
            if(i>=j)
                break;
            swap(nums[i], nums[j]);
        }
        swap(nums[low], nums[j]);
        return j;
    }
};