题目描述
传送门
拿出最少数目的魔法豆:给定一个正整数 数组beans ,其中每个整数表示一个袋子里装的魔法豆的数目。请你从每个袋子中拿出 一些豆子(也可以 拿出),使得剩下的非空袋子中(即至少还有一颗魔法豆的袋子)魔法豆的数目相等。一旦把魔法豆从袋子中取出,你不能再将它放到任何袋子中。
请返回你需要拿出魔法豆的最少数目。
我的解法
class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
if(beans.size() == 1) return 0;
sort(beans.begin(),beans.end());
long long res = LONG_MAX, temp = 0;
for(int i = 0 ; i < beans.size(); ++i){
temp = 0;
if(i > 0) temp = accumulate(beans.begin(), beans.begin() + i, 0);
for(int j = i + 1; j < beans.size(); ++j){
temp += (beans[j] - beans[i]);
}
if(temp < res){
res = temp;
}
}
return res;
}
};
思路
暴力求解,先对数组进行排序,然后从小到大分别以不同数量的豆子作为基准(非空袋子中剩下的豆子数量),求解答案。
结果
分析
时间复杂度:
O(n2)。
空间复杂度:
O(logn),即为排序的栈空间开销。
官方题解
class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
int n = beans.size();
sort(beans.begin(), beans.end());
long long total = accumulate(beans.begin(), beans.end(), 0LL); // 豆子总数
long long res = total; // 最少需要移除的豆子数
for (int i = 0; i < n; i++) {
res = min(res, total - (long long)beans[i] * (n - i));
}
return res;
}
};
分析
时间复杂度:
O(nlogn),排序算法。
空间复杂度:
O(logn),即为排序的栈空间开销。
查漏补缺
暴力算法超出时间范围,需要思考其他的解决方案。两次循环求和可以通过总数减去一定的值得到结果(需要自己多一份思考,而不是直接暴力求解)。
更新日期
2024.01.18文章来源:https://www.toymoban.com/news/detail-804914.html
参考来源
力扣链接文章来源地址https://www.toymoban.com/news/detail-804914.html
到了这里,关于算法刷题——拿出最少数目的魔法豆(力扣)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!