开发一款网站需要多少钱,wordpress文章列表不显示图片,创建全国文明城市方案,厦门小型网站建设文章目录 题目描述我的解法思路结果分析 官方题解分析 查漏补缺更新日期参考来源 题目描述
传送门 拿出最少数目的魔法豆#xff1a;给定一个正整数 数组beans #xff0c;其中每个整数表示一个袋子里装的魔法豆的数目。请你从每个袋子中拿出 一些豆子#xff08;也可以 拿… 文章目录 题目描述我的解法思路结果分析 官方题解分析 查漏补缺更新日期参考来源 题目描述
传送门 拿出最少数目的魔法豆给定一个正整数 数组beans 其中每个整数表示一个袋子里装的魔法豆的数目。请你从每个袋子中拿出 一些豆子也可以 拿出使得剩下的非空袋子中即至少还有一颗魔法豆的袋子魔法豆的数目相等。一旦把魔法豆从袋子中取出你不能再将它放到任何袋子中。 请返回你需要拿出魔法豆的最少数目。
我的解法
class Solution {
public:long long minimumRemoval(vectorint 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(vectorint 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
参考来源
力扣链接
