【排序算法运用】剑指 Offer 40. 最小的k个数-跟着帅地玩副业，开拓第二曲线PlayOffer

lQl 永久会员 2025年1月16日上午11:33

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        int len = stock.length;
        if (cnt == 0) {
            return new int[0];
        }
        quickSort(stock, 0, len - 1);
        int[] res = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            res[i] = stock[i];
        }
        return res;
    }

    public void quickSort(int[] stock, int l, int r) {
        if (l < r) {
            int pivot = stock[l];
            int i = l;
            int j = r;
            while (i < j) {
                while (i < j && stock[j] >= pivot) {
                    j--;
                }
                stock[i] = stock[j];

                while (i < j && stock[i] < pivot) {
                    i++;
                }
                stock[j] = stock[i];

            }
            stock[i] = pivot;
            quickSort(stock, l, i-1);
            quickSort(stock, i + 1, r);
        }
    }
}

时间复杂度O(nlogn)
空间复杂度O(logn)

0 赞同 0 条回复

Xiang. 永久会员 2024年12月22日下午3:30

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        quickSort(stock,0,stock.length-1);
        return Arrays.copyOf(stock,cnt);
    }
    void quickSort(int[] stock,int left,int right){
        if(left>=right) return;
        int l=left,r=right;
        int pivot=stock[left];
        int tmp;
        while(l<r){
            while(l<r&&stock[r]>=pivot) r--;
            while(l<r&&stock[l]<=pivot) l++;
            tmp=stock[r];
            stock[r]=stock[l];
            stock[l]=tmp;
        }
        stock[left]=stock[r];
        stock[r]=pivot;
        quickSort(stock,left,r-1);
        quickSort(stock,r+1,right);
    }
}
时间复杂度：O（nlogn）
空间复杂度：O（n）

0 赞同 0 条回复

陆狗陆狗普通 2024年12月19日下午10:56

解题思路
– 先排序再选择前面k个
– 问题的关键就变成了排序，这里使用堆排序，来练习一下堆排序
【题解1】

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        // 先排序再选择前面k个
        // 使用堆排序
        heapSort(stock);
        // 选择前面k个
        return Arrays.copyOf(stock, cnt);

    }

    public void heapSort(int[] stock) {
        // 1.写维护堆性质的方法
        // 2.建堆
        // 3.交换
        // 4.对交换后的新堆顶维护堆性质
        // 注意点，需要从1开始编号
        // 把数组转换成大顶堆
        int n = stock.length;
        // 建堆：从最后一个非叶子节点开始从下往维护堆的性质
        // 【错误】i--的这种，i>=0，而不是i<=0
        for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
            heapify(stock, i, n);
        }
        // 交换(i=0时，是最后一个不需要再交换了)
        for (int i = n - 1; i >= 1; i--) {
            // 交换
            swap(stock, i, 0);
            // 维护堆的性质
            heapify(stock, 0, i);
        }

    }

    public void heapify(int[] stock, int index, int n) {
        // 左右节点下标
        int leftIndex = 2 * index + 1;
        int rightIndex = 2 * index + 2;
        int largeIndex = index;
        if (leftIndex <= n - 1 && stock[leftIndex] > stock[largeIndex]) {
            largeIndex = leftIndex;
        }
        if (rightIndex <= n - 1 && stock[rightIndex] > stock[largeIndex]) {
            largeIndex = rightIndex;
        }
        // 确实最大金额不是父节点
        if (largeIndex != index) {
            swap(stock, index, largeIndex);
            // 交换后可能会影响堆的性质
            heapify(stock, largeIndex, n);
        }
    }

    public void swap(int[] stock, int a, int b) {
        int c = stock[a];
        stock[a] = stock[b];
        stock[b] = c;
    }
}

错误点1：i–的这种，i>=0，而不是i<=0

0 赞同 0 条回复

秋山丽奈普通 2024年12月17日下午8:16

思路：排序选择前 cnt

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        Arrays.sort(stock);
        return Arrays.copyOfRange(stock,0,cnt);

    }
}

0 赞同 0 条回复

Aatorx 永久会员 2024年12月17日下午4:01

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        vector<int> res;
        quicksort(stock, 0, stock.size() - 1);
        for(int i = 0; i < cnt; i++) {
            res.push_back(stock[i]);
        }
        return res;
    }
    void quicksort(vector<int>& stock, int l, int r) {
        if (l >= r) {
            return;
        }
        int x = l;
        int y = r;
        while(x < y) {
            while(x < y && stock[y] >= stock[l]) {
                y--;
            }
            while(x < y && stock[x] <= stock[l]) {
                x++;
            }
            swap(stock[x], stock[y]);
        }
        swap(stock[x], stock[l]);
        quicksort(stock, l, x - 1);
        quicksort(stock, x + 1, r);
    }
};

利用快速排序算法进行排序，返回数组前cnt个元素。
时间复杂度O(Nlogn)，空间复杂度O(N)。

0 赞同 0 条回复

jaron 普通 2024年12月17日上午10:34

方法一：快排，但每次只排一边，O(n)

方法二：堆排，大根堆，要插入的数比堆顶小，就弹出堆顶，O(nlogcnt)

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        int[] ans = new int[cnt];
        randomizedSelect(stock, cnt - 1);
        for (int i = 0; i < cnt; i++) {
            ans[i] = stock[i];
        }
        return ans;
    }

    // 如果arr排序的话，在i位置的数字是什么
    public static void randomizedSelect(int[] arr, int i) {
        int ans = 0;
        for (int l = 0, r = arr.length - 1; l <= r;) {
            // 随机这一下，常数时间比较大
            // 但只有这一下随机，才能在概率上把时间复杂度收敛到O(n)
            partition(arr, l, r, arr[l + (int) (Math.random() * (r - l + 1))]);
            // 因为左右两侧只需要走一侧
            // 所以不需要临时变量记录全局的first、last
            // 直接用即可
            if (i < first) {
                r = first - 1;
            } else if (i > last) {
                l = last + 1;
            } else {
                break;
            }
        }
    }

    // 荷兰国旗问题
    public static int first, last;

    public static void partition(int[] arr, int l, int r, int x) {
        first = l;
        last = r;
        int i = l;
        while (i <= last) {
            if (arr[i] == x) {
                i++;
            } else if (arr[i] < x) {
                swap(arr, first++, i++);
            } else {
                swap(arr, i, last--);
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

0 赞同 0 条回复

月下足迹普通 2024年12月17日上午9:39

//排序后取出cnt个数
public int[] inventoryManagement(int[] stock, int cnt) {
int [] result = new int [cnt];
Arrays.sort(stock);
for (int i = 0; i < cnt; i++) {
result[i] = stock[i];
}
return result;
}

0 赞同 0 条回复

迢迢星野普通 2024年12月16日下午9:36

class Solution {
    /**
     * 仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。
     * 
     * 题意解读：返回最小的 cnt 个商品，使用优先级队列，大顶堆实现
     * 方法一：排序 + 取出前 cnt 个元素
     * 方法二：大顶堆
     * 方法三：快排
     * 方法四：快速选择
     * @param stock
     * @param cnt
     * @return
     */
    public int[] inventoryManagement2(int[] stock, int cnt) {
        // 容量为 cnt 的大顶堆
        PriorityQueue<Integer> que = new PriorityQueue<>((a, b) -> b - a);

        // 每一个元素都需要进入大顶堆一遍，是为了将堆顶的元素删除（较大的元素）
        for (int elem : stock) {
            que.offer(elem);
            if (que.size() > cnt){
                que.poll();
            }
        }

        // 此时 que 的 cnt 个元素就所求结果
        int[] ans = new int[cnt];
        int i = 0;
        while (!que.isEmpty()) {
            ans[i++] = que.poll();
        }
        return ans;
    }


    public int[] inventoryManagement3(int[] stock, int cnt) {
        // 快排思想：选取基准元素，从左向右找到第一个比基准元素大的索引，从右向左找到第一个比基准元素小的索引，交换这两个索引的元素，递归左右子数组，直至整个数字有序
        quickSort(stock, 0, stock.length - 1);
        return Arrays.copyOf(stock, cnt);
    }

    private void quickSort(int[] nums, int l, int r) {
        // 长度为 1 时终止
        if (l >= r) return;
        // 哨兵划分操作，以 nums[l] 为基准数
        int i = l, j = r;

        while (i < j) {
            // 从右向左找到第一个比基准元素小的索引
            while (i < j && nums[j] >= nums[l]) j--;
            // 从左向右找到第一个比基准元素大的索引
            while (i < j && nums[i] <= nums[l]) i++;
            // 交换这两个元素
            swap(nums, i, j);
        }
        // 交换基准元素
        swap(nums, i, l);
        // 对左右子数组进行快排操作
        quickSort(nums, l, i - 1);
        quickSort(nums, i + 1, r);
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public int[] inventoryManagement(int[] stock, int cnt) {
        // 快速选择思想：将数组划分为最小的 cnt 个数和其他数组两部分即可，快速排序的哨兵划分可以完成此目标。
        // 快排的每次哨兵划分就可以确定该基准数在数组中的索引
        // 根据快排思想，如果某次哨兵划分后 基准数正好的第 cnt + 1 小的数字，那么此时基准数左边的所有数字便是题目所求的最小的 cnt 个数
        // 可以在每次哨兵划分后，判断基准数在数组中的所有是否等于 cnt，若 true 则直接返回此时数组的前 cnt 个数即可。
        if (cnt >= stock.length) return stock;
        return quickSort(stock, cnt, 0, stock.length - 1);
    }

    private int[] quickSort(int[] nums, int k, int l, int r) {
        int i = l, j = r;
        // 进行哨兵划分
        while (i < j) {
            while (i < j && nums[j] >= nums[l]) j--;
            while (i < j && nums[i] <= nums[l]) i++;
            swap(nums, i, j);
        }
        swap(nums, i, l);
        // 此时的 i 就是哨兵在数组中的索引
        if (k < i) {
            // k 在 i 左边，递归左子数组
            return quickSort(nums, k, l, i - 1);
        }else if (k > i) {
            // k 在 i 右边，递归右子数组
            return quickSort(nums, k, i + 1, r);
        }else {
            // i == k，返回前 k 个数
            return Arrays.copyOf(nums, k);
        }
    }
}

思路：大顶堆、快排、快速选择
时间复杂度：O(nlogn)、O(nlogn)、O(n)
空间复杂度：O(n)、O(n)、O(logn)

0 赞同 0 条回复

Kisara 普通 2024年12月16日下午6:55

这个题目就i是排序一下取数组前cnt个元素就好

快排思想：

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        if(stock==null||stock.length<=0) return new int[0];
        quickSort(stock,0,stock.length-1);
        List<Integer> result=new ArrayList<>();
        for(int i=0;i<cnt;i++){
            result.add(stock[i]);
        }

        return result.stream().mapToInt(Integer::intValue).toArray();


    }

    public void quickSort(int[] stock,int low,int high){
        if(low>=high) return ;
        int pivoit=stock[high];
        int i=low-1;
        for(int j=low;j<stock.length;j++){
            if(stock[j]<pivoit){
                i++;
                int temp=stock[i];
                stock[i]=stock[j];
                stock[j]=temp;
            }
        }
        int temp=stock[i+1];
        stock[i+1]=stock[high];
        stock[high]=temp;

        quickSort(stock,low,i);
        quickSort(stock,i+2,high);
    }
}

Ologn Ologn

堆排序

java Priorityqueue默认维护一个最小堆，二叉树的根节点一定是最小的，从而直接取cnt个根节点就可以完成题目

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for(int n:stock){
            queue.offer(n);
        }
        List<Integer> res=new ArrayList<>();
        for(int i=0;i<cnt;i++){
            if(!queue.isEmpty())
            res.add(queue.poll());
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}

OLogn O1

0 赞同 0 条回复

【排序算法运用】剑指 Offer 40. 最小的k个数

共以下 9 个回答

快排思想：

堆排序

# 回答此问题取消回复

【排序算法运用】剑指 Offer 40. 最小的k个数

共以下 9 个回答

快排思想：

堆排序

# 回答此问题 取消回复

# 回答此问题取消回复