题解 | #寻找第K大#

#include<algorithm>
class Solution {
public:
    //快速排序
    int findKth(vector<int> a, int n, int K) {
        return quickSelect(a,0,n - 1,n - K);
    }
    inline int randomPartition(vector<int>& a,int low,int high){
        int pivot = rand() % (high - low + 1) + low;
        swap(a[low],a[pivot]);
        pivot = low;
        while(low < high){
            while(low < high && a[high] >= a[pivot])
                high--;
            while(low < high && a[low] <= a[pivot])
                low++;
            swap(a[low],a[high]);
        }
        swap(a[low],a[pivot]);
        return low;
    }
    
    int quickSelect(vector<int>& a,int low,int high,int index){
        int pivot = randomPartition(a, low, high);
        if(pivot == index)
            return a[pivot];
        else if(pivot < index)
            return quickSelect(a, pivot + 1, high, index);
        else
            return quickSelect(a, low, pivot - 1, index);
    }
};