题解 | #寻找第K大#

class Solution {
  public:
    int go(int fi, int end, vector<int>& p, int k) {
        if (fi == end)return fi;
        int zd = p[rand()%(end-fi+1)+fi], l = fi, r = end;
        while (l < r) {
            while (p[l] > zd && l < r)l++;
            while (p[r] < zd && l < r)r--;
            swap(p[l], p[r]);
            l++;
        }
        if (r - fi >= k)return go(fi, r - 1, p, k);
        return go(r, end, p, k-r+fi);
    }
    int findKth(vector<int> a, int n, int K) {
        return (a[go(0, n - 1, a, K)]);
    }
};