个数(easy)"/>
[大根堆]面试题40. 最小的k个数(easy)
题目:
题解:
- 大根堆模板题,维持一个大小为 k 的大根堆就可得到数组前 k 个最小数了。
代码如下:
class Solution {
public:vector<int> getLeastNumbers(vector<int>& arr, int k) {if(!k)return {};priority_queue<int> heap;//维持大小为k的大根堆for(int a:arr){if(heap.size()<k)heap.push(a);else{if(heap.top()<=a)continue;//元素比堆顶元素值大,不需要添加到堆中else{heap.pop();heap.push(a);}}}vector<int> res;while(!heap.empty()){res.push_back(heap.top());heap.pop();}return res;}
};
更多推荐
[大根堆]面试题40. 最小的k个数(easy)
发布评论