Problem Description

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

version1.3 快排和排序结合 beat 27%

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int cnt=nums.size();
        int num;
        if(cnt>7)
            num=quickSort(nums,0,cnt-1,k);
        else{
            sort(nums.begin(),nums.end(),greater<int>());
            num=nums[k-1];
        }

        return num;
    }
    int quickSort(vector<int> &nums,int low,int high,int k){
    int pivot=low;//若只有一个数，此时要返回第一个值
    if(low<high){
        pivot=Partition(nums,low,high);

        if(k==(pivot+1))
            return nums[pivot];
        
        else if(k<(pivot+1))
            return quickSort(nums,low,pivot-1,k); //递归的返回值又忘了
        else
            return quickSort(nums,pivot+1,high,k);
    }
    return nums[pivot];
}

int Partition(vector<int> &nums,int low,int high){
    int pivotNum=nums[low];
    while(low<high){
        while(low<high&&nums[high]<=pivotNum) high--;
        swap(nums[low],nums[high]);
        while(low<high&&nums[low]>=pivotNum)  low++;
        swap(nums[low],nums[high]);
    }
    return low;
}
};

version1.3 快排 beat 65% 靠。。。。竟然比不上纯快排

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int cnt=nums.size();
        int num;
            sort(nums.begin(),nums.end(),greater<int>());
            num=nums[k-1];
        return num;
    }
   

version1.4 堆 beat 58% 靠。。。。竟然比不上堆

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int cnt=nums.size();
        int num;
            sort(nums.begin(),nums.end(),greater<int>());
            num=nums[k-1];
        return num;
    }
   

注意事项

1.第k大的数，快排原先是从小到大排序
2.递归的时候返回值，与昨天同样的错误
3.轴值最后要交换，特殊情况，只有一个值的时候，递归后只有一个值得时候