leetcode-215

数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

思路

找到数组中第k大的元素，可以直接排序，再找，但效率太低，不考虑
想到快速排序的每一趟排序，排完后基准值所在的位置右边若有n个元素，基准值就是第n+1大，如果n+ 1 == k，那基准值就是我们要找的元素，如果n+ 1 > k，那我们要查找的值一定在基准值的右侧，反之则是左侧，因此我们可以利用快排来缩小范围以便查找

代码

class Solution {
public:
    int partition(vector& nums,int start,int end){
        int pivot = nums[end];
        int i= start;
        for(int j = start;j < end;j++){      //顺序快排
            if(nums[j] <= pivot){
                swap(nums[i++],nums[j]);
            }
        }
        swap(nums[end],nums[i]);
        return i;
    }
    int quickSelect(vector& nums,int start,int end,int k){
        int i = rand()% (end-start+1)+start;      //生成随机种子，优化快排
        swap(nums[i],nums[end]);

        int q = partition(nums, start, end);
        if (q == k) {
            return nums[q];
        } else {
            return q < k ? quickSelect(nums, q + 1, end, k) : quickSelect(nums, start, q - 1, k);       //缩小范围的重点
        }
    }
    int findKthLargest(vector& nums, int k) {
        srand(time(NULL));
        return quickSelect(nums,0,nums.size()-1,nums.size()-k);//注意这里传入的是nums.size()-k,这样quickSelect里面就可以直接与之比较，不用转化了
    }
};