题解 | 寻找第K大

class Solution {
public:
    /**
        find Kth element in 'a' in range [lh, rh)
    */
    int findKth(vector<int> &a, int lh, int rh, int K) {
        if(rh - lh == 1) {
            return a[lh];
        }

        int pivot = lh;
        int index = lh + 1;
        for(int i = index; i < rh; ++i) {
            if(a[i] < a[pivot]) {
                swap(a, index, i);
                ++ index;
            }
        }
        int rank = rh - index + 1;
        if(rank == K) {
            return a[pivot];
        } else if(rank < K) {
            return findKth(a, pivot + 1, index, K - rank);
        } else {
            // rank > K
            return findKth(a, index, rh, K);
        }
    }
    
    /**
        swap a[i1] and a[i2]
    */
    void swap(vector<int> &a, int i1, int i2) {
        int tmp = a[i1];
        a[i1] = a[i2];
        a[i2] = tmp;
    }


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param n int整型 
     * @param K int整型 
     * @return int整型
     */
    int findKth(vector<int>& a, int n, int K) {
        // write code here
        auto a_clone = a;
        return findKth(a, 0, a.size(), K);
    }
};

快排思路，易错点在于边界