给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
解题思路一：堆排序
这道题就是很经典的 topK 问题啦，就是实现一个小根堆，注意不是大根堆，因为实现了小根堆之后，我们可以通过条件限制，将比堆顶大的元素进堆，如果比堆顶小的话，那么就没必要进堆了，最后遍历完数组之后，我们规定堆的元素大小是 k 个，那么此时堆顶是 k 个元素中最小的，那么不就是所有元素中第 k 大的吗，对不对，很简单！
下面代码中我们就直接用 stl 中的 priority_queue 来创建一个小根堆：
int findKthLargest(vector<int>& nums, int k)
{
priority_queue<int, vector<int>, greater<int>> pq; // 创建一个小根堆
for(int i = 0; i < k; ++i)
pq.push(nums[i]);
for(int i = k; i < nums.size(); ++i)
{
if(nums[i] > pq.top())
{
pq.pop();
pq.push(nums[i]);
}
}
return pq.top();
}解题思路二：快速选择算法
上面的解法很优秀的，但是时间复杂度还是达不到题目要求的 O(n)，所以我们要换一种算法，也就是快速选择算法，它的时间复杂度可以达到 O(n) 级别，这是算法导论经过数学分析推导的，这里就不推导了，比较复杂！
快速选择算法，其实和前面的快速排序是类似的，也是通过分治的思想，只不过对分治后的处理稍作改动罢了！
按照之前的快速排序那样子的分治，根据一个随机基准值 key，假设第一次分类完毕，最后分为了三个部分，如下所示
那么根据上图中已知的 left、i、right 三个指针，我们也是能确定三个区间各自的元素个数的，假设这里它们各自的元素个数分别是 a、b、c，如下图所示：
另外上面的 LEFT 和 RIGHT 指针指的是当前递归区间的范围（不一定是从零到数组末尾的，所以需要有这两个指针）
此时我们就想哈，既然我们要去找第 k 个最大元素，也就是从后往前找到第 k 个元素，此时第 k 个元素会有三种情况：
- 如果
k ≤ c的话：- 说明该元素存在于
[right, RIGHT]区间，所以我们前面的区间也就是[LEFT, right - 1]区间就可以不用考虑了，但是此时留下来的区间还是无序的，所以继续递归大于key的这个区间去分治即可！
- 说明该元素存在于
- 如果
k ≤ b + c的话：- 说明该元素存在于
(left, right)区间内，这种情况是最容易处理的，因为这个区间内的元素都是相等的，此时我们直接返回该区间的任一元素即可，不需要再去递归进行分治了！
- 说明该元素存在于
- 当上面都不成立的话：
- 说明该元素存在于
[LEFT, left]区间，所以后面的区间也就是[left + 1, RIGHT]区间就可以不用考虑了，而继续递归小于key的这个区间去分治，只不过此时k的值需要变一下（因为我们是从后往前找元素的，所以去掉后面的区间了，递归传入的区间就变了，所以k当然也要变化），根据上面的元素个数和区间关系，可以得到k = k - b - c。
- 说明该元素存在于
而上面的 b = right - left - 1，c = RIGHT - right + 1，是比较容易得到的！
注意别混淆，上面只是中间等于 key 的区间是有序（相等也是一种有序），而左右两边小于或者大于 key 的区间，是还没有排完序的，所以需要继续递归下去分治！
class Solution {
public:
// 获取随机基准值
int partition(vector<int>& nums, int LEFT, int RIGHT) { return nums[(rand() % (RIGHT - LEFT + 1)) + LEFT]; }
// 快速选择算法
int quick_select(vector<int>& nums, int LEFT, int RIGHT, int k)
{
// 如果只有一个元素或者越界的话，直接返回nums[LEFT]即可
if(LEFT >= RIGHT)
return nums[LEFT];
// 依旧是快排的分三块思想
int key = partition(nums, LEFT, RIGHT);
int i = LEFT, left = LEFT - 1, right = RIGHT + 1;
while(i < right)
{
if(nums[i] < key)
swap(nums[++left], nums[i++]);
else if(nums[i] == key)
i++;
else
swap(nums[--right], nums[i]);
}
// 根据k的情况分类讨论
int b = right - left - 1, c = RIGHT - right + 1; // 这是中间和右边区间的元素个数
if(k <= c)
return quick_select(nums, right, RIGHT, k);
else if(k <= b + c)
return key;
else
return quick_select(nums, LEFT, left, k - b - c);
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(nullptr));
return quick_select(nums, 0, nums.size() - 1, k);
}
};