Day6-线性表-堆-数组中第K大的数
一 先唠两句
下午从5点开始需求评审开了仨小时，去食堂吃完饭回来又赶紧干活，毕竟节前要上线，最近确实有点忙的手忙脚乱，盒饭更的稍微简短一些，不过干货肯定还是少不了的???
二 直接上题
Q：已知一个未排序的数组，求数组中第K大的数
如：array = 【3，2，1，5，6，4】，k = 2，那么结果就是5
三 完整代码及运行结果
冷静分析：
如果你这时候对面试官说，把数组排序，再倒着取第k个不就行了，那你一定没考虑到，排序后数组中的数依然可能有重复，这种情况。
所以记住就好：关于第k大，第k小的，前k个，等等，这种问题，甭想，面试官一定想问你的是，堆。
基础知识回顾：
二叉堆，c++中的STL优先级队列，即priority queue，最大（小）值先出的完全二叉树。
那么问题来了，完全二叉树又是什么？
哈哈哈哈哈这个会在树章节中讲到~
用优先级队列它的好处就是，当我们push或者pop数的时候，它会自动帮我们调整堆依然为最大（小）堆。
附：最小堆构造方法
priority queue＜int，vector＜int＞，greater＜int＞＞less_heap
即less_heap就是我们要的最小堆了
push 将数据压入堆
pop 弹出堆顶元素
empty 判断堆是否为空
size 返回堆中元素个数
top返回堆顶元素
把上面初始化中的greater换成less，就是最大堆的构造方法。
回到题目当中，我们需要维护一个k大小的最小堆，先将前k个元素压入堆，继续遍历数组，当，当前数组元素大于堆顶元素时，就把当前数组元素压入堆（当然要先弹出当前堆顶元素）。这样遍历结束以后，堆顶就是第k个大的元素了。
拿题目举例
3压入堆[3]
2压入堆并自动调整[2，3]
1比当前堆顶2，小，不操作
5比2大，弹出2压入5并调整，[3，5]
6比堆顶3大，弹出3压入6并调整，[5，6]
4比堆顶5，小，不操作
最后的大小为2的，最小堆，[5，6]
堆顶元素5，即为第2大的数???
且不说要是不用堆，用排序后，倒着取k个，能不能实现，我用堆，就遍历一遍，时间复杂度n，你选时间复杂度最低的排序算法，nlogn，而且排序完后还要再操作，心累不???
好了，理解堆之后你就会发现非常简单~
栈和队列，我建议大家动手实现一些基本题，比如用栈实现队列，用队列实现栈，可以帮助大家更好理解栈和队列，我就不更这些基本题了~至于更难的题，比如用栈实现一个计算器，有点过于麻烦，面试中被问的概率极低，所以我会慢慢搜罗一些栈和队列的题，就先更了堆~
今天的盒饭就到这，赶快动手实现，理解就很简单???
//
// Created by renyi on 2019/6/4.
//
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int findKthLargest(vector<int>& nums, int k){
priority_queue<int, vector<int>, greater<int> > less_heap;//初始化一个最小堆
for (int i = 0; i < nums.size(); i++) {
if (less_heap.size() < k){//如果最小堆中元素个数，小于k个，直接push入堆
less_heap.push(nums[i]);//保证是一个k大小的最小堆
} else if(less_heap.top() < nums[i]){
less_heap.pop();//当堆顶元素小于当前元素，那么当前元素更大一些，所以push入堆。当然首先将堆顶元素弹出。
less_heap.push(nums[i]);
}
}
return less_heap.top();//堆顶即为第K大的数
}
int main(){
vector<int> nums;
for (int i = 0; i < 10; i++){
nums.push_back(rand() % 100);
}
printf("the start nums is:");
for (int i = 0; i < 10; i++) {
printf("%d ", nums[i]);
}
printf("\n");
int result = findKthLargest(nums, 4);
printf("the 4th largest num is:%d\n", result);
return 0;
}
运行结果
