题解 | #寻找第K大#

快排每次可以确定最终有序序列的一个位置i，若改位置就是要找到第K大，则返回，若改数小于第K大，处理右边，否则，处理左边。size - i就是第（size - i）大的数。

class Solution {
public:
    int idx;
    int size;
    int findKth(vector<int> a, int n, int K) {
        // write code here
        idx = K;
        size = n;
        return qsort(a,0,n-1);
    }

    int qsort(vector<int> &arr,int left,int right){
        int i = left,j = right;
        int base = arr[left];
        while (i < j) {
            while (arr[j] >= base && i <j) j--;
            while(arr[i] <= base && i < j) i++;
            if (i < j){
                swap(arr[i],arr[j]);
            }
        }
        swap(arr[left],arr[i]);
        //此时已确定排序中第i大的数
        if (size - i == idx) {
            return arr[i];
        }else if(size- i < idx){
            return qsort(arr, left, i - 1);//处理左边
        }else{
            return qsort(arr, i+1, right);//处理右边
        }
    }
};