当前位置: 首页 > article >正文

Day16:最小的k个数

仓库管理员以数组 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]

LCR 159. 库存管理 III - 力扣(LeetCode)

首先考虑用TreeSet来实现这个代码,因为TreeSet会基于红黑树自动帮我们排序。

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        for(int i = 0; i < stock.length; i++){
            treeSet.add(stock[i]);
        }

        // 取出最小的 cnt 个元素
        int[] result = new int[cnt];
        int index = 0;
        for (int num : treeSet) {
            if (index < cnt) {
                result[index++] = num;
            } else {
                break; // 已经取够 cnt 个元素,退出循环
            }
        }

        return result;
    }
}

很明显,不合适,因为Set集合会去重。

下面改用快排,快排的时间复杂度为O(n),刚好复习一下快排的代码。

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

    public void quickSort(int[] stock, int low, int high){
         if (low < high) {
            // 找到分区点
            int partitionIndex = partition(stock, low, high);

            // 递归排序左半部分
            quickSort(stock, low, partitionIndex - 1);

            // 递归排序右半部分
            quickSort(stock, partitionIndex + 1, high);
        }
    }

    public int partition(int[] stock, int low, int high){
        //找到基准元素
        int pivot = stock[low];
        int left = low + 1;   //左指针
        int right = high;  //右指针
        while(left <= right){
            while(left <= right && stock[right] > pivot){
                right--;
            }
            while(left <= right && stock[left] < pivot){
                left++;
            }

            if(left <= right){
                swap(stock,left,right);
                left++;
                right--;
            }
        }
        swap(stock,right,low);
        return right;
    }

    private void swap(int[] stock, int i, int j) {
        int temp = stock[i];
        stock[i] = stock[j];
        stock[j] = temp;
    }

}

快排的核心全在partition算法里,本质是确定分区点,每一次分区就代表这个元素被排好了。

我们分析一下改怎么写,如何确定最后return的是左边还是右边。

我们把最左端定为哨兵,也就是说最后的位置左边必须比哨兵小,右边必须比哨兵大。while循环的条件是left<=right。首先收缩边界,然后交换,最后的情况是right指着最后一个小于或等于 pivot 的元素。因此要pivot和right换。


http://www.kler.cn/a/587175.html

相关文章:

  • craftjs的示例landing项目改成APP路由
  • 我与DeepSeek读《大型网站技术架构》- 总结
  • 【零基础入门unity游戏开发——unity3D篇】物理系统 —— 3D物理材质Physics Material
  • 解锁下一代AI应用:开源项目mcp-server-qdrant如何重塑向量数据库管理?
  • EasyCVR安防视频汇聚平台助力工业园区构建“感、存、知、用”一体化智能监管体系
  • 异步加载错误如何解决
  • Linux 中 Git 使用指南:从零开始掌握版本控制
  • Flexus应用服务器L实例、X实例以及ECS(弹性计算服务)之间的区别及其适用场景
  • 函数的引用/函数的默认参数/函数的占位参数/函数重载
  • 【C++】:STL详解 —— 布隆过滤器
  • 设计心得——多态
  • 【VUE】day03-vue过滤器、计算属性、vue-cli、vue组件
  • java 中判断对象是否可以被回收和 GCROOT
  • DataWhale学习--大语言模型--模型发展历程
  • go 加载yaml配置文件
  • 成为Python砖家(7): 使用miniforge管理Python版本
  • STM32 HAL库实战:高效整合DMA与ADC开发指南
  • Unity学习日志番外:简易行为树
  • 金融时间序列分析(Yahoo Finance API实战)
  • Java构造方法详解:从入门到实战