题解 | #寻找第K大#

class Solution {
public:

    void swap(int &a, int &b) {
        int temp = a;
        a = b;
        b = temp;
    }
    
    int _qS(vector<int> &arr, int l, int r) {
        swap(arr[l], arr[(l+r)/2]);    // 选区间中间的点，避免极端情况导致时间复杂度达到n2
        int temp = arr[l];
        while(l < r) {
            while(l < r && arr[r] >= temp) --r;
            arr[l] = arr[r];
            while(l < r && arr[l] <= temp) ++l;
            arr[r] = arr[l];
        }
        arr[l] = temp;
        return l;
    }
    
    void qS(vector<int> &arr, int l, int r, int target) {
        if(l < r) {
            int mid = _qS(arr, l, r);
            if(mid == target) return;
            else if(mid > target) qS(arr, l, mid, target);    //只往一个方向递归
            else qS(arr, mid+1, r, target);
        }
    }
    
    int findKth(vector<int> a, int n, int K) {
        // write code here
        if(n == 0) return -1;
        qS(a, 0, n-1, n-K);
        return a[n-K];
    }
};