数组中第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素

快排思想, 每次取一个划分位置, 类似于二分

int partion(std::vector<int> &v, int low, int high){
    int key=v[low];
    while(low<high){
        while(low<high && v[high]>=key) high--;
        v[low]=v[high];
        while(low<high && v[low]<=key) low++;
        v[high]=v[low];
    }
    v[low]=key;
    return low;
}

int findKthLargest(vector<int>& nums, int k) {
        int index= nums.size()-k;
        int part = partion(nums, 0, nums.size()-1);
        while(part!=index){
            if(part<index)
                part = partion(nums,part+1, nums.size()-1);
            else
                part = partion(nums, 0, part-1);
        }
        return nums[index];
    }