数组中的第K个最大元素

解法一：优先队列（堆）

时间复杂度：O(n log k) 空间复杂度：O(k)

手动维护一个大小为 k 的最小堆（堆顶是堆中的最小元素），每当堆的大小超过 k 时，就将堆顶的元素弹出，这样最终留下来的堆顶元素就是第k大的元素

 1int findKthLargest(vector<int>& nums, int k)
 2{
 3    std::priority_queue<int, std::vector<int>, greater<int>> pq;
 4    for(const int& num : nums)
 5    {
 6        pq.emplace(num);
 7        if(k < pq.size())
 8            pq.pop();
 9    }
10    return pq.top();
11}

解法二：快速选择

平均时间复杂度是 O(n)

常规情况下的快排的平均时间复杂度是nlogn，所以需要手写一个快排

具体实现：

定义三个数组，分别存储大于、等于、小于基准值的数，通过一轮循环将其填充

之后的判断存在三种情况：

1.k 小于等于 big 数组的大小——也就是说，big数组中存在第一大、第二大…..一直到第 k 大甚至更多元素，此时第 k 大的元素一定存在于 big 数组中，那么接下来就只需要在 big 数组里寻找即可

2.k 大于原数组大小减去 small 数组大小——nums.size() - small.size() 代表的是 big 数组加上 equal 数组的大小，也就是说此时 big 与 equal 数组中的元素数量加起来都不足 k 个，那么第 k 大的元素就一定在 small数组里了；注意 quickSeclet 的第二个参数从 k 变成了 k - nums.size() + small.size()，这是因为，相对于整个数组，需要寻找的是第 k 大的元素，而相对于 small 数组来说，这个元素是第

k - （nums.size() - small.size()）大的元素

3.第 k 大位于 equal里面

此时直接返回基准值即可

 1int findKthLargest(vector<int>& nums, int k)
 2{
 3    return quickSeclet(nums, k);
 4}
 5
 6int quickSeclet(vector<int>& nums, int k)
 7{
 8    std::vector<int> big, equal, small;
 9    int pivot = nums[std::rand() % nums.size()];
10    for(int num : nums)
11    {
12        if(num < pivot) small.push_back(num);
13        else if(pivot < num) big.push_back(num);
14        else equal.push_back(num);
15    }
16
17    if(k <= big.size())
18        return quickSeclet(big, k);
19    if(nums.size() - small.size() < k)
20        return quickSeclet(small, k - nums.size() + small.size());
21    return pivot;
22}