AcWing 53. 最小的k个数
原题链接
简单
作者:
daniellee
,
2019-04-10 21:19:05
,
所有人可见
,
阅读 1232
C++ 代码
class Solution {
public:
int n;
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
n = input.size();
vector<int> res;
for(int i=0;i<n;i++){
if(i<k) insert(res, input[i]);
else{
if(input[i]<res[0]){
res[0]=input[i];
push_down(res, k-1, 0);
}
}
}
sort(res.begin(), res.end());
return res;
}
void push_down(vector<int> &a, int size, int u){
int t=u, l=u*2+1, r=u*2+2;
if(l<=size && a[l]>a[t]) t=l;
if(r<=size && a[r]>a[t]) t=r;
if(t!=u){
swap(a[u], a[t]);
push_down(a, size, t);
}
}
void push_up(vector<int> &a, int u){
if(!u) return;
while((u-1)/2>=0 && a[u]>a[(u-1)/2]){
swap(a[u], a[(u-1)/2]);
u=(u-1)/2;
}
}
void insert(vector<int> &a, int x){
a.push_back(x);
push_up(a, a.size()-1);
}
};