题解 | #最小的K个数#

手写小根堆，注意数组下标从1开始，因此将数组第一个元素push back到最后。

#include <climits>
#include <vector>
class Solution {
public:
    void down(vector<int> &input, int k, int sz) {
        int t = k;
        if (2 * k < sz && input[2 * k] < input[t]) t = 2 * k;
        if (2 * k + 1 < sz && input[2 * k + 1] < input[t]) t = 2 * k + 1;
        if (t != k) {
            swap(input[t], input[k]);
            down(input, t, sz);
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if (!input.size() || !k || input.size() < k) return res;
        input.emplace_back(input[0]); // 使数组下标从1开始

        int sz = input.size() - 1;

        for (int i = sz / 2; i; --i) down(input, i, sz);
        for (int i = 1; i <= k; ++i) {
            res.push_back(input[1]);
            input[1] = input[sz];
            down(input, 1, sz);
            --sz;
        }
        return res;
    }
};