2024.1.18力扣每日一题——拿出最少数目的魔法豆

题目来源

力扣每日一题；题序：2171

我的题解

方法一 排序+前缀和

结果与原始顺序无关，因此先进行排序，然后计算前缀和。
有官方题解证明：最终在 拿出最少数目的魔法豆 的前提下，一定是以某个袋子中豆子数为保留值的。因此，以每个袋子作为保留值进行遍历查找最优。

时间复杂度：O(n)
空间复杂度：O(n)

public long minimumRemoval(int[] beans) {
    Arrays.sort(beans);
    int n=beans.length;
    long[] preSum=new long[n+1];
    for(int i=0;i<n;i++){
        preSum[i+1]=preSum[i]+beans[i];
    }
    long res=Long.MAX_VALUE;
    for(int i=0;i<n;i++){
        //左边的需要全部置为0
        long left=preSum[i];
        //右边是   总和-左边的值-当前值*（n-i）  当前值*（n-i）表示右侧都变为beans[i]后最终保留的元素和
        long right=preSum[n]-preSum[i]-(1l*beans[i]*(n-i));
        //比较大小
        res=Math.min(res,left+right);
    }
    
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法二 优化版本

根据方法一中的求解来看，left+right后与preSum[i]无关，只与preSum[n]有关，因此可以只求总和，不在计算前缀和。

时间复杂度：O(n)
空间复杂度：O(1)

public long minimumRemoval(int[] beans) {
    Arrays.sort(beans);
    int n=beans.length;
    long sum=Arrays.stream(beans).asLongStream().sum();
    long res=Long.MAX_VALUE;
    for(int i=0;i<n;i++){
        //比较大小
        res=Math.min(res,sum-(1l*beans[i]*(n-i)));
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈