题解 | #最小的K个数#

此题提示应该是要我们用堆排序，但是由于这题只有整数，并且有相同的数据，同时空间复杂度要求也不高，个人觉得堆排序或许更方便一些。

class Solution {
  public:
    int* maxmin_vec(vector<int> v) {
        int max = v[0], min = v[0];
        for (int i = 1; i < v.size(); i++) {
            max = (v[i] > max) ? v[i] : max;
            min = (v[i] < min) ? v[i] : min;
        }
        int* maxmin = new int[2];
        maxmin[0] = max;
        maxmin[1] = min;
        return maxmin;
    }
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        if (input.empty() || input.size() <= k) return input;
        vector<int> res, tmp;
        if (!k) return res;
        unordered_map<int, vector<int>> bucket;
        int* range = maxmin_vec(input);
        int num = range[0] - range[1] + 1; //桶的数量
        for (int i = 0; i < input.size(); i++) {
            bucket[input[i] - range[1]].push_back(input[i]);
        }
// 由于都是整数，每个桶只有相同数值的数
        for (int i = 0; i < num; i++) {
            if (bucket[i].size() + res.size() <= k) {
                res.insert(res.end(), bucket[i].begin(), bucket[i].end());
            } else {
                res.insert(res.end(), bucket[i].begin(), bucket[i].begin() + k - res.size());
            }
        }
        return res;
    }
};