2024.1.18
题目来源
我的题解
方法一 排序+前缀和
结果与原始顺序无关，因此先进行排序，然后计算前缀和。
有官方题解证明：最终在 拿出最少数目的魔法豆 的前提下，一定是以某个袋子中豆子数为保留值的。因此，以每个袋子作为保留值进行遍历查找最优。
时间复杂度：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;
}
方法二 优化版本
根据方法一中的求解来看，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;
}
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
