题目描述
输入 $n$ 个整数,找出其中最小的 $k$ 个数。
注意:
输出数组内元素请按从小到大顺序排序;
数据范围
$1≤k≤n≤1000$
样例
输入:[1,2,3,4,5,6,7,8] , k=4
输出:[1,2,3,4]
算法1:排序后返回前 $k$ 个数
时间复杂度:$O(n\log n+k)$
C++代码
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
sort(input.begin(),input.end());
return vector<int>(input.begin(),input.begin() + k);
}
};
算法2:用堆来维护前 $k$ 小的数
用大根堆,当堆的大小超过 $k$ 时就把堆顶元素弹出
时间复杂度:$O(n\log k)$
C++代码
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
priority_queue<int> heap;
for(auto x : input)
{
heap.push(x);
if(heap.size() > k) heap.pop();
}
vector<int> output;
while(heap.size()) output.push_back(heap.top()),heap.pop();
return vector<int> (output.rbegin(),output.rend());
//相当于先reverse再返回
}
};