题目描述

输入n个整数，找出其中最小的k个数。

样例

输入：[1,2,3,4,5,6,7,8] , k=4

输出：[1,2,3,4]

算法

(大顶堆)

1. 这道题求最小的k个数，我们用大顶堆来维护。
2. 为什么用堆呢？因为不能保证输入数组是排好序的，它可能是乱序的，而堆可以自动排好序。
3. 我们不断地往heap中添加元素，比如前4个元素，都会放进堆中。遍历到第5个元素的时候，堆顶是前4个元素的最大值，如果最大值top比第5个元素x大，则应该删除这个top，因为该数组中这个top并不是前k个小的数之一。然后如果第6个数比新的top大，那么第6个元素是不会care的，因为我们只存比top小的。比top大的只会在heap中元素不够k个的时候进入，而且如果不合法，因为后面会一直push元素，这些先进堆的但是比较大的元素，还是会被pop出去
4. 因为是大顶堆，所以是逆序，因为输出前要reverse一下。

时间复杂度

$O(nlogk)$
在堆中插入元素是$O(logk)$，因为堆中有k个元素。然后因为会把n个元素都遍历一遍，插入到heap中，可能每个插入的元素都会进入堆中，所以n个元素，就是$O(nlogk)$的时间复杂度。

C++ 代码

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> heap;
        for(auto x : input)
        {
            if(heap.size() < k || heap.top() > x) heap.push(x);
            if(heap.size() > k) heap.pop();
        }

        vector<int> res;
        while(heap.size()) res.push_back(heap.top()), heap.pop();
        reverse(res.begin(), res.end());

        return res;
    }
};