目录
2171. 拿出最少数目的魔法豆
题目描述:
实现原理与解析:
排序 + 前后缀
原理思路:
2171. 拿出最少数目的魔法豆
题目描述:
给定一个 正整数 数组 beans
,其中每个整数表示一个袋子里装的魔法豆的数目。
请你从每个袋子中 拿出 一些豆子(也可以 不拿出),使得剩下的 非空 袋子中(即 至少还有一颗 魔法豆的袋子)魔法豆的数目 相等。一旦把魔法豆从袋子中取出,你不能再将它放到任何袋子中。
请返回你需要拿出魔法豆的 最少数目。
示例 1:
输入:beans = [4,1,6,5] 输出:4 解释: - 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。 剩下袋子中魔法豆的数目为:[4,0,6,5] - 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为:[4,0,4,5] - 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。 剩下袋子中魔法豆的数目为:[4,0,4,4] 总共拿出了 1 + 2 + 1 = 4 个魔法豆,剩下非空袋子中魔法豆的数目相等。 没有比取出 4 个魔法豆更少的方案。
示例 2:
输入:beans = [2,10,3,2] 输出:7 解释: - 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为:[0,10,3,2] - 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为:[0,10,3,0] - 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。 剩下袋子中魔法豆的数目为:[0,10,0,0] 总共拿出了 2 + 2 + 3 = 7 个魔法豆,剩下非空袋子中魔法豆的数目相等。 没有比取出 7 个魔法豆更少的方案。
提示:
1 <= beans.length <= 105
1 <= beans[i] <= 105
实现原理与解析:
排序 + 前后缀
C++
class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
int n = beans.size();
sort(beans.begin(), beans.end());
long long res = LONG_MAX;
long long pre_sum = 0;
vector<long long> suf(beans.size() + 1); // 后缀,表示以beans[i]为标准,需要去除的豆子个数
long long j = 1; // 可以想象一下图,是很多矩形组成,这个j就是长度,差值是高度
for (int i = n - 2; i >= 0; i--, j++) {
suf[i] = (beans[i + 1] - beans[i]) * j + suf[i + 1];
}
for (int i = 0; i < n; i++) {
long long cur = pre_sum;
pre_sum += beans[i];
res = min(res, cur + suf[i]);
}
return res;
}
};
Java
class Solution {
public long minimumRemoval(int[] beans) {
Arrays.sort(beans);
int n = beans.length;
long[] suf = new long[n];
long j = 1;
for (int i = n - 2; i >= 0; i--, j++) {
suf[i] = (beans[i + 1] - beans[i]) * j + suf[i + 1];
}
long res = Long.MAX_VALUE;
long pre = 0;
for (int i = 0; i < n; i++) {
long cur = pre;
pre += beans[i];
res = Math.min(res, cur + suf[i]);
}
return res;
}
}
原理思路:
理解题目,其实就算选中一个袋子,大于其豆子数量的袋子减去响应豆子变成和其一样的,小于的直接清零。所以很明显,我们需要排序。
如果直接循环,根据数据范围,会超时,所以利用前后缀先预处理出选取不同i的前缀和,以及后缀,当然后缀取的是,需要去掉的豆子总和,在求后缀时,可以想象一下二维矩形图,其实是就是很多小矩形组成,这个j就是长度,差值是高度。
这里我前缀直接在遍历的时候再求的,也可以提前求出来,是一样的。文章来源:https://www.toymoban.com/news/detail-807296.html
最后遍历一下就行,注意开long long。文章来源地址https://www.toymoban.com/news/detail-807296.html
到了这里,关于LeetCode:2171. 拿出最少数目的魔法豆(C++、Java 排序 + 前后缀)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!