方法一：快排（适用于数据量较少的情况下）o(2n)

class Solution {
public:
    void quick_sort(int l, int r, int k, vector<int>& input)
    {
        if (l == r) return;
        int i = l - 1, j = r + 1, x = input[i + j >> 1];
        while (i < j)
        {
            do i++; while (input[i] < x);
            do j--; while (input[j] > x);
            if (i < j) swap(input[i], input[j]);
        }
        // quick(l, j), quick(j + 1, r)
        if (j >= k - 1) quick_sort(l, j, k, input);
        else quick_sort(j + 1, r, k, input);
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if (input.size() == 0 || input.size() < k) return vector<int>{};

        quick_sort(0, input.size() - 1, k, input);
        vector<int> res;
        for (int i = 0; i < k; i++) res.push_back(input[i]);
        return res;
    }
};

方法二：堆排序（适用于数据量较大的情况下）o(nlog(k))

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if (input.size() == 0 || input.size() < k || k == 0) return vector<int>{};

        priority_queue<int, vector<int>, less<int>> q;
        for (int i = 0; i < input.size(); i++)
        {
            if (q.size() < k || q.top() > input[i])
            {
                q.push(input[i]);
                if (q.size() > k) q.pop();
            }
        }

        vector<int> res;
        while (!q.empty())
        {
            res.push_back(q.top());
            q.pop();
        }
        return res;
    }
};