数组中的第k个最大元素

（小黎最近在忙刷题，网课先告一段落！绝对不鸽！咕咕咕

给定整数数组nums和整数k，请返回数组中第k个最大的元素。

提示：

• 1 <= k <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4

215.数组中的第K个最大元素

这个主要就是用到了快排的思想啦！随机选择数组中的一个数作为key，之后将比key小的数放到它的右边，比它大的放左边。（因为要第k大嘛！如果要第k小的话就比它大的反过来就好啦！）

排序完之后，如果key刚好在第k个的位置的话，直接返回就好啦。如果key的下标小于k - 1（这里是用于下标从0开始计算的语言哦！下标从1开始的语言要变一下哦，灵活变一下啦），那么所求元素在key的右边，继续对右边进行相同的操作；如果key的下标大于k - 1，那么所求元素在key的左边，继续对左边进行相同的操作。

快速排序的性能和划分出的子数组的长度密切相关。直观地理解就是，如果每次规模为$n$的问题我们都划分成$1$和$n - 1$，每次递归的时候又向$n - 1$的集合中递归，这种情况是最坏的，时间代价是$O(n ^ 2)$。我们可以引入随机化来加速这个过程，它的时间代价的期望是$O(n)$，证明过程可以参考「《算法导论》9.2：期望为线性的选择算法」。

放上小黎的代码！

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand((unsigned)time(NULL));
        int n = nums.size();
        return getKth(nums, k - 1, 0, n - 1);
    }

    int getKth(vector<int>& nums, int k, int left, int right){
        if(right != left){
            int random = rand() % (right - left) + left;
            swap(nums[random], nums[right]);
        }
        int idx = partition(nums, left, right);
        if(idx == k){
            return nums[idx];
        }else if(idx > k){
            return getKth(nums, k, left, idx - 1);
        }else if(idx < k){
            return getKth(nums, k, idx + 1, right);
        }
        return -1;
    }

    int partition(vector<int>& nums, int left, int right){
        int begin = left - 1;
        int key = nums[right];
        for(int i = left; i < right; ++i){
            if(nums[i] > key){
                swap(nums[++begin], nums[i]);
            }
        }
        swap(nums[++begin], nums[right]);
        return begin;
    }
};

执行用时：4ms，超过了97%的cpp提交记录
内存消耗：9.6MB，超过了90%的cpp提交记录