public:
int temp[10005];
void merge(vector<int>& input,int left,int right){
if(left==right)return ;
int mid=(left+right)/2;
merge(input,left,mid);
merge(input,mid+1,right);
Allmerge(input,left,mid,right);
}
void Allmerge(vector<int>& input,int left,int mid,int right){
for(int i=left;i<=right;i++){
temp[i]=input[i];
}
int i=left;
int j=mid+1;
for(int k=left;k<=right;k++){
if(i==mid+1){
input[k]=temp[j];
j++;
}
else if(j==right+1){
input[k]=temp[i];
i++;
}
else if(temp[i]>=temp[j]){
input[k]=temp[j];
j++;
}
else if(temp[i]<temp[j]){
input[k]=temp[i];
i++;
}
}
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
//归并排序
if(input.size()>0)//易错,为空就不要进去了
merge(input,0,input.size()-1);
vector<int>res;
for(int i=0;i<k;i++){
res.push_back(input[i]);
}
return res;
}
};