题目描述

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

注意：

• 数据保证 k 一定小于等于输入数组的长度;
• 输出数组内元素请按从小到大顺序排序;

样例

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

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

算法

(小根堆) $O(n)$

用小根堆存储数组中的每个数，从堆顶弹出 k 个数即可

时间复杂度

遍历数组的时间复杂度为 $O(n)$，从堆中弹出 k 个数的时间复杂度为 $O(k)$，所以总时间复杂度为 $O(n)$

C++ 代码

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        priority_queue<int, vector<int>, greater<int>> heap;

        for (auto x : input) heap.push(x);
        while (k -- ) res.push_back(heap.top()), heap.pop();
        return res;
    }
};