题解 | #最小的K个数#
最小的K个数
https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> ret;
if(k == 0 || k > input.size())
return ret;
priority_queue<int, vector<int>> pq;
for(int val : input){
if(pq.size()<k)
pq.push(val);
else{
if(val < pq.top()){
pq.pop();
pq.push(val);
}
}
}
while(!pq.empty()){
ret.push_back(pq.top());
pq.pop();
}
return ret;
}
};
优先队列模拟大根堆
每次与堆顶元素比较，若比堆顶元素小，则将堆顶元素出堆，当前元素入堆
- 最小n个数：大根堆，比堆顶小则加入
- 最大n个数：小根堆，比堆顶大则加入
