题解 | #寻找第K大#

1.partition算法

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        K = K-1;
        int p = -1;
        int start=0,end = a.size()-1;
        while(true) {
            p = partition(a,start,end);
            if(p==K) {
                return a[K];
            }
            if (p<K){
                start = p+1;
            } else {
                end = p-1;
            }
        }
    }
    

    int partition(vector<int>& a,int start,int end) {
        if(start>=end) {
            return start;
        }
        int x = a[end];
        int i = start-1;
        for(int j=start;j<end;j++){
            if(a[j] > x ) {
                i++;
                swap(a[i],a[j]);
            }
        }
        swap(a[i+1],a[end]);
        return i+1;
    }
};