最小的k个数

1.直接使用sort()函数

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int>ret;
        if(k==0||k>input.size())
            return ret;
        sort(input.begin(),input.end());
        return vector<int>({input.begin(),input.begin()+k});
    }
};

2.快排

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(k==0||k>input.size())
            return {};
        vector<int>ret;
        int l=0,r=input.size();
        while(l<r){
            int mid=partition(input,l,r);
            if(mid+1==k)
                return vector<int>({input.begin(),input.begin()+k});
            else if(mid+1<k)
                l=mid+1;
            else
                r=mid;
        }
        return ret;
    }
    int partition(vector<int> &input,int l,int r){
        int povit=input[r-1];
        int tmp=l;
        for(int i=l;i<r-1;i++){
            if(input[i]<povit){
                swap(input[tmp++],input[i]);
            }
        }
        swap(input[r-1],input[tmp]);
        return tmp;
    }
};

3.堆排

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>>maxk;
        for(int i=0;i<input.size();i++){
            if(maxk.size()<k){
                maxk.push(input[i]);
            }
            else{
                if(input[i]<maxk.top()){
                    maxk.pop();
                    maxk.push(input[i]);
                }
            }
        }
        while(!maxk.empty()){
            ret.push_back(maxk.top());
            maxk.pop();
        }
        return ret;
    }
};

4.归并排序，但注意：归并排序需要对原始数组进行更新

class Solution {
public:
    vector<int>ret;
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(k==0||k>input.size())
            return {};
        ret.resize(input.size());
        mergesort(input,0,input.size()-1);
        return vector<int>({ret.begin(),ret.begin()+k});
    }
    void mergesort(vector<int>& input,int l,int r){
        if(l>=r)
            return;
        int mid=(r+l)/2;
        mergesort(input,l,mid);
        mergesort(input,mid+1,r);
        Merge(input,l,mid,r);
    }
    void Merge(vector<int>& input,int l,int mid,int r){
        int i=l,j=mid+1;
        int k=l;
        while(i<=mid&&j<=r){
            if(input[i]<input[j]){
                ret[k++]=input[i++];
            }
            else
                ret[k++]=input[j++];
        }
        while(i<=mid)
            ret[k++]=input[i++];
        while(j<=r)
            ret[k++]=input[j++];
        //很重要，归并排序需要对原始数组进行更新
        for(int i=l;i<=r;i++){
            input[i]=ret[i];
        }
    }
};