题目来源
力扣2171拿出最少数目的魔法豆
题目概述
给定一个 正整数 数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。
请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少还有一颗 魔法豆的袋子）魔法豆的数目 相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。文章来源：https://www.toymoban.com/news/detail-809645.html
请返回你需要拿出魔法豆的 最少数目。文章来源地址https://www.toymoban.com/news/detail-809645.html
解题思路
- 剩余的豆子数量肯定是某一个袋中豆子的数量（如果不是的话，其他数量大于这个袋子的需要拿出更多， 这个袋子也需要拿出，结果肯定大于这个袋子不拿出的）。
- 遍历每一种剩余的可能求最小结果。
代码实现
java实现
public class Solution {
public long minimumRemoval(int[] beans) {
// 袋子数量
int length = beans.length;
// 对每个袋子里的豆子数排序
Arrays.sort(beans);
// 记录总兜子数
long total = 0;
for (int bean: beans) {
total += bean;
}
// min记录移除数量
// 默认移除全部的豆子
long min = total;
int lastRest = 0;
for (int i = 0; i < length; i++) {
if (beans[i] == lastRest) continue;
// beans[i]为剩余数量， length - i 表示有多少袋子数量大于剩余数量
// 剩余数量 * 大于剩余数量的袋子数就是最终剩余多少豆子
// current表示需要移除的豆子数
long current = total - (long) beans[i] * (length - i);
min = Math.min(min, current);
lastRest = beans[i];
}
return min;
}
}
c++实现
class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
// 袋子数量
int length = beans.size();
// 对每个袋子里的豆子数排序
sort(beans.begin(), beans.end());
// 记录总兜子数
long long total = 0;
for (int bean : beans) {
total += bean;
}
// min记录移除数量
// 默认移除全部的豆子
long long min = total;
int lastRest = 0;
for (int i = 0; i < length; i++) {
if (beans[i] == lastRest) continue;
// beans[i]为剩余数量， length - i 表示有多少袋子数量大于剩余数量
// 剩余数量 * 大于剩余数量的袋子数就是最终剩余多少豆子
// current表示需要移除的豆子数
long long current = total - (long long)beans[i] * (length - i);
min = min < current ? min : current;
lastRest = beans[i];
}
return min;
}
};
到了这里，关于【力扣每日一题】力扣2171拿出最少数目的魔法豆的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
