题解 | #寻找第K大#

题目

题解：使用快排

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        return quickSort(a, 0,a.size()-1,K);
    }
    int quickSort(vector<int> v,int low,int high,int k)
    {
        //if(low>high)return 0;
        int start=low,end=high,key=v[low];
        while(start<end)
        {
            while(end>start && v[end]<=key)end--;//找到第一个比key大的数字
            if(end>start)
            {
                int tmp=v[end];
                v[end]=v[start];
                v[start]=tmp;
                start++;
            }
            while(end>start && v[start]>=key)start++;//找到第一个比key小的数字
            if(end>start)
            {
                int tmp=v[start];
                v[start]=v[end];
                v[end]=tmp;
                end--;
            }
        }
        if(start==k-1)return v[start];//找完一趟看是否当前哨兵是第K大数字
        else if(start>k-1)return quickSort(v, low,start-1,k);//第K大数字在哨兵左侧
        else return quickSort(v, start+1,high,k);//第K大数字在哨兵右侧
    }
};