40.最小的k个数

参考链接

剑指offer_在线编程_牛客网

剑指 Offer 40. 最小的k个数-跟着帅地玩转校招，刷爆各类算法题帅地玩Offer

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

个人尝试 ❌

自己写了遍快速排序，好多bug...

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        if(stock == null || stock.length == 0 || cnt == 0) return new int[0];
        sort(stock, 0, stock.length - 1);
        //重新遍历
        int[] res = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            res[i] = stock[i];
        }
        return res;
    }

    //快排
    public void sort(int[] arr, int start, int end) {
        //终止条件
        // ❌,修改:
        // if (start >= end) return;
        if (start == end) return ;
        
        int base = arr[start];
        //❌,修改:
        //int i = start, j = end;
        int i = arr[start + 1], j = arr[end];
        while (i < j) {
            //❌,修改:
            //while (i < j && arr[j] >= base) j--;
            while (i < j && arr[i] < base) i++;
            //❌,修改:
            //while (i < j && arr[i] <= base) i++;
            while (i < j && arr[j] > base) j++;
            if (i < j) {
                swap(arr, i, j);
            }
        }
        if (start != i) swap(arr, start, i);
        sort(arr, start, i - 1);
        sort(arr, i + 1, end);
    }
    //交换
    public void swap(int[] arr, int x, int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
}

优秀题解

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;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/solutions/594591/jian-zhi-offer-40-zui-xiao-de-k-ge-shu-j-9yze/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。