题解 | #寻找第K大#

W
    获取第K大在排序后数组位置
        快排
            获取随机分区间点
                循环当l<r
                    如果就是K,直接返回值
                    判断在分区点左右
                        左
                            r=p-1;
                        右
                            l=p+1
N
    左闭右闭区间划分
    没有找到return -1;

class Solution {
public:
    int fn; 
    int quickfindK(vector<int>& nums,int l,int r){


        while(l<=r){
            int p=partition(nums, l,r);
            if(p<fn){
                 l=p+1;//第k大元素在nums[p+1  r]里
            }
            else if(p>fn){
                 r=p-1;
            }
            else if(p==fn){
                return nums[p];//找到第k最大元素
            }
        }

        return -1;//没有找到或区间不符合

    }
    int partition(vector<int>& nums ,int l,int r){
        srand(time(nullptr));
        int x=rand()%(r-l+1)+l;
        swap(nums[r],nums[x]);
        int pivot=nums[r];
        int i=l,j=l;
        for(;j<r;j++){
            if(nums[j]<pivot){
                swap(nums[i],nums[j]);
                i++;
            }

        }
        swap(nums[i],nums[r]);
            return i;
    }
    int findKth(vector<int>& nums, int n,int k) {
        fn=nums.size()-k;//note 处理  
        if(n==1){
            return nums[0];
        }
        return quickfindK(nums,0,nums.size()-1);

    }
};