题解 | #最小的K个数#

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(input.size()<=k) return input;
        return qsort(input, k,0, input.size()-1);
    }
    vector<int> qsort(vector<int>& input,int k,int l,int r){
        int i = l,j = r;
        while(i<j){
            while(i<j && input[j]>=input[l]) j--;
            while(i<j && input[i]<=input[l]) i++;
            swap(input[i],input[j]);
        }
        swap(input[i],input[l]);
        if(i>k) qsort(input, k, l, i-1);
        if(i<k) qsort(input, k, i+1, r);
        vector<int> res;
        res.assign(input.begin(),input.begin()+k);
        return res;
    }
};