题解 | #寻找第K大# 快速搜索

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        return quickfind(a, 0, n-1, K);
    }
     
    int quickfind(vector<int>& a, int left, int right, int k) {
        int i = left;
        int j = right;
        int mark = a[left];
         
        while (i < j) {
            while (i < j && a[j] >= mark)
                --j;
            
             
            while (i < j && a[i] <= mark)
                ++i;
          
            if (i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        a[left] = a[i];
        a[i] = mark;
        
         
        //哨兵右侧比他大的数字个数
        int big_num = right - i;
        
        //如果哨兵刚好是第K大的数
        if (k - big_num - 1 == 0)
            return mark;
        else if (k - big_num - 1 > 0) {
            //如果右侧数字个数不够K个，则从左侧找第k-big_num-1大的数
            return quickfind(a, left, i - 1, k - big_num - 1);
        } else {
            //如果右侧数字个数比K多，则在右侧找第K大的数
            return quickfind(a, i + 1, right, k);
        }
    }
};