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;
}

运行结果