215.数组中的第K个最大元素
题目阐述：
给定整数数组nums和整数k,请返回数组中第k个最大的数组。
请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素
Eg1:
input: [3,2,1,5,6,4] 和 k = 2
output: 5
Eg2:
input: [3,2,3,1,2,4,5,5,6] 和 k = 4
output: 4
notes:
1 <= k <= nums.length <= 104-104 <= nums[i] <= 104
解题思路
这道题刚拿到手，看到难度竟然是一道中等题目
开始想：既然我已经学过了C++ stl库,这道题真的是太简单了，直接sort呗。
但为了给这道题一点面子。。这里会用到三种方法来解决这个看似非常简单的问题
解题是主要的，但是我们也不能忽视了效率问题，所以最后会好好地总结一下这三个方法的优良差异
1. 直接暴力排序
就像刚刚说的，直接用stl库里面的sort(快排)，对整个数组进行一个排序。
因为sort中,默认为排升序
所以最后返回的应该是下标为 (数组长度 - k)
代码如下:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
return nums[nums.size() - k];
}
};
2. 建堆
有一个同样在stl库里常用的容器————priority_queue（优先级队列)
它会在每次我们插入push数据，删除pop数据，自动执行AdjustUp和AdjustDown进行建堆。
思路：既然我们要找的是第k个最大的元素
那么我们就构建一个大堆，然后构造k-1次堆就行了（什么意思呢，我们知道，大堆的每次构建，最上面的top返回值都是当前最大的数字，要找第k个，那么我们只需要构建k-1次堆即可）
想清楚了这个思路，这道题就可以解了XD
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> q(nums.begin(),nums.end());
for(int i = 0;i < k - 1;i++)
{
q.pop();
}
return q.top();
}
};
3. 建堆（优化）
这里其实严格意义来说不能说算是优化，只是说对待不同的情况，这两种方法都得去考虑到
之前学堆的时候看到过一个问题，关于如何海量信息处理
这道题其实还好，题目给的例子都非常的温柔。
但如果让你从10000个数据里面找寻第100个最大的元素
这可够要命的
要知道建堆一次的时间复杂度为O(N)
数量大起来就成了O(N^N),这样问题就很大了
这样就衍生出第三种方法：
既然是海量数据，考虑到我们的问题就是建堆上面的时间复杂度问题，那么我们就想办法少建几次堆呗.
我们现在的问题可以转化成这样：
找最大的前k个数
思路：我们先建立一个k个元素大小组成的小堆，然后其余数字x每每和堆头top作比较，大的话就将堆pop掉，然后将x压入堆内。
具体代码如下：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int,vector<int>,greater<int>> q(nums.begin(),nums.begin()+k);
for(size_t i = k;i < nums.size();i++)
{
if(nums[i] > q.top())
{
q.pop();
q.push(nums[i]);
}
}
return q.top();
}
};
复杂度分析:
1.
第一个办法太简单粗暴了
直接一次快排，时间复杂度为O(N*logN)
2.
第二个方法要计算时间复杂度的话，我们得先知道建堆和向下调整算法的各自时间复杂度
建堆的时间复杂度为: O(N)
向下调整算法为: O(logN)
这里可以直接看我的blog
里面有详细计算解释
那么我们计算一下：
建堆需要O(N),要popK次，那么向下调整算法需要O(K*logN)
加起来就是O(N+K*logN)
第二种方法不仅仅是时间复杂度上面的问题，还同时要考虑空间复杂度。
这里建了一个N个数的堆，因为堆的底层就是用一个vector存起来，所以空间复杂度为O(N)
3.
第三个方法也不难计算
首先时间复杂度也是那两项：
建堆+向下调整
这里的向下调整是O((N-K)*logK)
我们这里的N-K已经是最差的情况了
这样时间复杂度就为O(N+(N-K)*logK)
而空间复杂度为O(K)
分析
这样一来我们就不去考虑第一种的方法了，只看第二和第三种。
当N和K相差不大的时候，其实这两者在时间上的效率和空间上的复杂度并不是相差特别大
但是相差大的时候，时间复杂度还好，空咋复杂度就拉开很大的差距了，一个只需要建立K个大小的，另外一个却要建立N个
这就是第三个方法为啥是最优的！