题解 | #最小的K个数#

class Solution {
  public:
    vector<int> so(int l, int r, vector<int>& input) {
        if (l > r) {
            vector<int>k;
            return k;
        }
        if (l == r) {
            vector<int>k;
            k.push_back(input[l]);
            return k;
        }
        vector<int>le = so(l, (l + r) >> 1, input);
        vector<int>ri = so(((l + r) >> 1) + 1, r, input);
        vector<int>ans;
        int l1 = 0, l2 = 0;
        while (l1 < le.size() && l2 < ri.size()) {
            if (le[l1] < ri[l2])ans.push_back(le[l1++]);
            else ans.push_back(ri[l2++]);
        }
        if (l1 < le.size())for (; l1 < le.size(); l1++)ans.push_back(le[l1]);
        if (l2 < le.size())for (; l2 < ri.size(); l2++)ans.push_back(ri[l2]);
        return ans;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        input = so(0, input.size() - 1, input);
        vector<int>ans;
        for (int i = 0; i < k && i < input.size(); i++)
            ans.push_back(input[i]);
        return ans;
    }
};