题解 | #寻找第K大#

class Solution {
public:
    //二分法确定某个值的最终位置，然后判断这个位置和要找的位置关系，选择往左或往右继续找
    int partition(vector<int> a,int left,int right,int k)
    {
        int ll=left,rr=right;
        int prot=a[left];
        while(left<right)
        {
            while(left<right&&a[right]<=prot)
                right--;
            a[left]=a[right];
            while(left<right&&a[left]>prot)
                left++;
            a[right]=a[left];
        }
        a[left]=prot;
        if(left<k-1)
        {
            return partition(a,left+1,rr,k);
        }else if(left>k-1){
            return partition(a,ll,left-1,k);
        }else{
            return a[left];
        }
    }
    int findKth(vector<int> a, int n, int K) {
        // write code here
        return partition(a,0,n-1,K);

    }
};