题解 | #寻找第K大#

思路

快排的思想，partition函数的使用。
如果返回的pivot>n-K，那么right = pivot-1
如果返回的pivot<n-K，那么left = pivot+1
进行新一轮的partition，直到pivot = n-K

代码

class Solution {
public:

    int partation(vector<int>& a, int L, int R){
        int left = L;
        int right = R;
        int key = a[left];
        while(left<right){
            while(left< right && a[right]>=key){
                right--;
            }
            a[left] = a[right];

            while(left< right && a[left]<=key){
                left++;
            }
            a[right] = a[left];
        }

        a[left] = key;

        return left;
    }
    int findKth(vector<int> a, int n, int K) {
        // write code here
        int left = 0;
        int right = n-1;
        while(1){
            int part = partation(a, left, right);
            if(part==n-K){
                return a[n-K];
            }
            else if(part>n-K){
                right = part-1;
            }
            else{
                left = part+1;

            }
        }
        return -1;

    }

};