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

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

大家看到这道题很高兴的调用了sort(),也有手搓快排的那么时间复杂度都在O(nlgn)

我们仔细想想快排的思想 本质上是在划分 那么我们先愉快的写一个划分吧

注意这里要从大到小了

int partition(vector
    
     & nums, int l,int r){        int temp = nums[l];        while(l < r){            int temp = nums[l];            while(l < r){                while(l < r && nums[r] <= temp) r--;                swap(nums[l],nums[r]);                while(l < r && nums[l] >= temp) l++;                swap(nums[l],nums[r]);            }        }        nums[l] = temp;        return l;    }
    

这里我们执行了一次划分操作，即把基准temp放在了一个位置，基准前的都比基准大，基准后的都比基准小 l就是基准最后所在的位置

那么这是想一想 如果l刚好和k-1相等(假设数组下标从0开始) 那么基准不就是要找的数字吗(前面有k-1个比他大的 他就是第k大的) 我们就可以愉快的返回了；如果 l > k-1那么很不幸运，我们的基准选的有点小了 造成基准是第k+eps(eps=1、2...)个大的元素，那么我们就在[left,l-1]这个区间找找；反正，基准选大了，就在[l+1,right]里面找找

int search(vector
    
     & nums,int l,int r,int k){        int m =partition(nums,l,r);        if(m == k-1) return nums[m];        else if(m > k-1) return search(nums,l,m-1,k);        else return search(nums,m+1,r,k);    }
    

这样就解决了问题。

我们并没有对数组进行排序，而是根据情况递归的寻找第k大的数，因此复杂度是比快排本身要低的，为O(n)。

但是如果数组本身就是有序的情况下，复杂度还是会飙升至O(n^2 )

关于这个问题的详细复杂度分析可以看看算导的第九章

完整函数代码 想尝试的可以移步leetcode

int partition(vector
    
     & nums, int l,int r){        int temp = nums[l];        while(l < r){            int temp = nums[l];            while(l < r){                while(l < r && nums[r] <= temp) r--;                swap(nums[l],nums[r]);                while(l < r && nums[l] >= temp) l++;                swap(nums[l],nums[r]);            }        }        nums[l] = temp;        return l;}int search(vector
     
      & nums,int l,int r,int k){        int m =partition(nums,l,r);        if(m == k-1) return nums[m];        else if(m > k-1) return search(nums,l,m-1,k);        else return search(nums,m+1,r,k);}int findKthLargest(vector
      
       & nums, int k) {        int length = nums.size();        if(k > length) return 0;        else return search(nums,0,length-1,k);}