【LetMeFly】2171.拿出最少数目的魔法豆：排序 + 枚举
力扣题目链接：https://leetcode.cn/problems/removing-minimum-number-of-magic-beans/
给你一个 正 整数数组 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 <= 1051 <= beans[i] <= 105
方法一：排序 + 枚举
二话不说先将豆子数量从小到大排个序。
统计一下一共有多少个豆子（即为all）。
遍历每个袋子中豆子的数量（假设当前豆子数量为bean），计算将小于bean的袋子移空、大于等于bean的袋子移为bean所需移除的豆子总数。
返回所有总数中的最小值即为答案。
时间复杂度
O
(
l
e
n
(
b
e
a
n
s
)
)
O(len(beans))
O(len(beans))空间复杂度
O
(
l
e
n
(
b
e
a
n
s
)
)
O(len(beans))
O(len(beans))
AC代码
C++
class Solution {
public:
long long minimumRemoval(vector
sort(beans.begin(), beans.end());
long long all = accumulate(beans.begin(), beans.end(), 0LL);
long long ans = all;
for (int i = 0; i < beans.size(); i++) {
ans = min(ans, all - ((long long)beans.size() - i) * beans[i]);
}
return ans;
}
};
Python
# from typing import List
class Solution:
def minimumRemoval(self, beans: List[int]) -> int:
beans.sort()
all_ = sum(beans)
ans = all_
for i, thisBean in enumerate(beans):
ans = min(ans, all_ - thisBean * (len(beans) - i))
return ans
同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~ Tisfy：https://letmefly.blog.csdn.net/article/details/135682601
精彩文章
您阅读本篇文章共花了：
发表评论