题解 | #最小的K个数#

class Solution {
public:
    int partition(vector<int> &input,int l,int r){
        int pivot = input[l];
        int i = l;
        for(int j = i + 1;j <= r;++j)
            if(input[j] <= pivot)
                swap(input[++i],input[j]);
        swap(input[i],input[l]);
        return i;  //返回中界点
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ans;
        if(k == 0 || input.size() < k)
            return ans;
//         sort(input.begin(),input.end());
//         for(int i = 0;i < k;++i)
//             ans.push_back(input[i]);
//         return ans;
        int left = 0,right = input.size() - 1;
        while(1){
            int mid = partition(input,left,right);
            if(mid == k)
                return vector<int>({input.begin(),input.begin() + k });
            else if(mid > k)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return ans;
    }
};