题解 | #最小的K个数#

class Solution {
  public:
  //快排的划分函数
    int Divide(vector<int>& arr, int left, int right) {
        int tmp = arr[left];
        while (left < right) {
            while (left < right && tmp < arr[right]) --right;
            if (left < right) arr[left] = arr[right];
            while (left < right && tmp >= arr[left]) ++left;
            if (left < right) arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }
//寻找第几小
    int  FindminK(std::vector<int>&arr, int left, int right, int k) {
        if (left == right && k == 1) return arr[left];
        else {
            int pos = Divide(arr, left, right);
            int j = pos - left + 1;
            if (j == k) return arr[pos];
            else if (k > j)  return FindminK(arr, pos + 1, right, k - j); //右边
            else return  FindminK(arr, left, pos - 1, k);
        }
    }
//找到第几小，前面均小于arr[k],将前面的放在一个新的容器并返回
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int > kong;
        if(k==0) return kong;
        FindminK(input,0,input.size()-1,k);
        std::vector<int>v(input.begin(),input.begin()+k);
        return v;
    }
};