[数组排序] LCR 159. 库存管理

1. 题目链接

LCR 159. 库存管理 III - 力扣（LeetCode）

2. 题目大意

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。

请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

3. 示例

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

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

4. 解题思路

对原数组从小到大排序后取出前 cnt 个数即可。

5. 参考代码

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        quickSort(stock, 0, stock.length - 1);
        return Arrays.copyOf(stock, cnt);
    }
    private void quickSort(int[] stock, int l, int r) {
        // 子数组长度为 1 时终止递归
        if (l >= r) return;
        // 哨兵划分操作（以 stock[l] 作为基准数）
        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, j);
        }
        swap(stock, i, l);
        // 递归左（右）子数组执行哨兵划分
        quickSort(stock, l, i - 1);
        quickSort(stock, i + 1, r);
    }
    private void swap(int[] stock, int i, int j) {
        int tmp = stock[i];
        stock[i] = stock[j];
        stock[j] = tmp;
    }
}