仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

示例 1：

**输入：**stock = [2,5,7,4], cnt = 1
输出：[2]

示例 2：

**输入：**stock = [0,2,3,6], cnt = 2
输出：[0,2] 或 [2,0]

提示：

0 <= cnt <= stock.length <= 10000

0 <= stock[i] <= 10000

使用快速排序的思想：

快排是选择一个基准数，然后将所有小于基准数的值移到基准数左边，大于基准数的值移到基准数右边

满足“左子数组任意元素<=基准数<=右子数组任意元素”

然后再分别对基准数左右两边进行排序

本题只要最小的cnt个值，所以只要 基准数的索引==cnt-1，就有左子数组满足要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> inventoryManagement(vector<int> &stock, int cnt) {
        vector<int> ans;
        qsort(stock, 0, stock.size() - 1, cnt);
        for (int i = 0; i < cnt; i++)
            ans.push_back(stock[i]);
        return ans;
    }
    void qsort(vector<int> &stock, int l, int r, int cnt) {
        if (l >= r)
            return;
        int i = l, j = r;
        while (i < j) {
            while (i < j && stock[j] >= stock[l]) // 必须先从右往左找
                j--;
            while (i < j && stock[i] <= stock[l])
                i++;
            swap(stock[i], stock[j]);
        }
        swap(stock[l], stock[i]);
        if (i + 1 == cnt)
            return;
        qsort(stock, l, i - 1, cnt);
        qsort(stock, i + 1, r, cnt);
    }
};

选择最左值为基准值必须先从右往左找

因为如果先从左往右找，i一定会先位于大于基准值的位置上（先出while），但是j无法保证与i相遇前位于小于基准值的位置上，会导致i，j相遇时处于大于基准值位置；