题解 | #寻找第K大# C++ 解法，快排 partition O(n)

题解 | #寻找第K大#
C++ 解法，快排 partition O(n)

class Solution {
public:
    void my_findkth(vector<int> &a, int l, int r, int K) {
        if (l >= r) return ;
        int x = l, y = r, z = a[((long long)l + r) >> 1];
        do {
            while (a[x] > z) ++x;
            while (a[y] < z) --y;
            if (x <= y) {
                swap(a[x], a[y]);
                ++x, --y;
            }
        } while (x <= y);
        if (K - 1 <= y) {
            my_findkth(a, l, y, K);
        } else if (K - 1 >= x) {
            my_findkth(a, x, r, K);
        }
        return ;
    }
    int findKth(vector<int> a, int n, int K) {
        my_findkth(a, 0, n - 1, K);
        return a[K - 1];
    }
};