leetcode LCR 159. 库存管理 III(easy)(小林出品必属精品)

2023-12-27 21:16:05

链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

代码:

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        //逐步找出 stock 数组的 0,stock.length-1 区间内最小的 cnt 个数,将其移动到数组前方
        qSelect(stock,0,stock.length-1,cnt);
        int[]ret=new int[cnt];
        //将前 cnt 个数据取出
        for(int i=0;i<cnt;i++){
            ret[i]=stock[i];
        }
        return ret;
    }

    public void qSelect(int[]stock,int l,int r,int cnt){
        //递归出口
        if(l>=r){
            return;
        }
        //随机选取一个基准元素 key ,将数组分为 3 部分
        int key=stock[new Random().nextInt(r-l+1)+l];

        int left=l-1,right=r+1,i=l;
        while(i<right){
            if(stock[i]<key){
                left++;
                swap(stock,i,left);
                i++;
            }else if(stock[i]==key){
                i++;
            }else{
                right--;
                swap(stock,i,right);
            }
        }

        //计算每个部分的数据个数
        int a=left-l+1;
        int b=right-left-1;
        int c=r-right+1;

        if(cnt<a){
            //在 < key 区间找最小的 cnt 个数,将小的数移动到前面
            qSelect(stock,l,left,cnt);
        }else if(cnt==a||cnt<=a+b){
            //代表 < key 区间的所有数据以及部分 = key 区间的数据是符合要求的,即前 cnt 个数是最小的
            return;
        }else{
            //在 >key 区间找最小的 cnt - a - b 个数,<key 和 =key 区间内的数据已经是符合条件的了
            qSelect(stock,right,r,cnt-a-b);
        }
    }

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

题解:

? ? ? ? 该题简单来说就是去获取数组中最小的 cnt 个数,解决该问题有很多的方法,可以将数组直接排好序,返回最小的 cnt 个数,时间复杂度为 O(nlogn),也可以使用大根堆来辅助解决,时间复杂度也为O(nlogn),该题我们采用的是快速选择的方法,时间复杂度能达到 O(n)

? ? ? ? ?快速选择方法的核心就是快速排序的核心,要先随机取一个基准数据 key,按照基准数据 key 将数组划分为 3 个区间,分别是 > key , = key ,< key 的区间,这样就可以把小的数据往前放,根据每个区间的数据个数,判断最小的 cnt 个数在哪些区间,再去这些区间用同样的方式把小的数据往前放,当最小的 cnt 个数都被放到数组最前面时,直接返回前 cnt 个数据即可

? ? ? ? 1.首先我们需要随机取一个基准数据 key,按照基准数据 key 将数组划分为 3 个区间,分别是 > key , = key ,< key 区间,该过程推荐看leetcode 75. 颜色分类(medium)(优质解法),这里就不赘述了

? ? ? ? 2.将数组划分为 3 个区间以后如下图所示:

? ? ? ? 其中 a,b,c 分别代表对应区间的数据个数,由图可知,a = left - L?+ 1 , b = right - left - 1 , c = R?- right + 1?

? ? ? ? 题目要求找最小的 cnt 个数,所以先在 < key 的区间找,当

? ? ? ? cnt < a 时 ,最小的 cnt 个数在 <key 区间,所以我们可以不管 =key 和 >key 区间,直接去 < key 区间找最小的 cnt 个数,按照相同的方法进行划分,将小的数移至数组前方(递归

? ? ? ? cnt = a 或 cnt <= a + b 时,代表 < key 区间的所有数据都是符合条件的,=key 区间的数据部分符合条件,但 = key 区间的数据都为 key,顺序不重要,这代表数组中前 cnt 个数据已经是满足条件的了,直接 return 即可

? ? ? ? 不是上述情况的话,最小的 cnt 个数就会包含在 <key,=key >key 三个区间中,此时?<key和=key 区间的数据都是符合条件的,已经找到了 a+b 个最小的数据,只需要在 >key 区间中找到最小的 cnt - a - b 个数据即可,按照相同的方法进行划分,将小的数移至数组前方(递归

????????

????????

文章来源:https://blog.csdn.net/q322359/article/details/135248946
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。