题目描述
输入 n 个整数，找出其中最小的 k 个数。
注意：
- 输出数组内元素请按从小到大顺序排序;
数据范围
1≤k≤n≤1000
样例
输入：[1,2,3,4,5,6,7,8] , k=4 输出：[1,2,3,4]
方法一：堆排序 O(nlogk)
这道题可以利用大根堆的性质来做（大顶堆的堆顶是该堆中所有元素的最大值）：
- 将数组中所有元素都放入大根堆中，由于大根堆堆顶是最大的元素，所以只要堆中元素数量大于
k，就pop出去，这样最终堆中得到的元素是前k小的元素。 - 用一个数组接收堆中元素的输出。
- 因为每次放入的都是最大元素，所以数组中元素是从大到小，最后还需要翻转一下顺序。
class Solution { public: vector<int> getLeastNumbers_Solution(vector<int> input, int k) { priority_queue<int, vector<int>> q; //大根堆 for (auto x : input) { q.push(x); if (q.size() > k) q.pop(); //堆中元素个数大于k时，开始弹出堆顶即最大的元素 } vector<int> ans; while (q.size()) ans.push_back(q.top()), q.pop(); reverse(ans.begin(), ans.end()); //将数组调整成从小到大的顺序 return ans; } };
欢迎大家在评论区交流~
