本文最后更新于 200 天前,其中的信息可能已经有所发展或是发生改变。
给定一个 正整数 数组 beans
,其中每个整数表示一个袋子里装的魔法豆的数目。
请你从每个袋子中 拿出 一些豆子(也可以 不拿出),使得剩下的 非空 袋子中(即 至少还有一颗 魔法豆的袋子)魔法豆的数目 相等。一旦把魔法豆从袋子中取出,你不能再将它放到任何袋子中。
请返回你需要拿出魔法豆的 最少数目。
提示:
1 <= beans.length <= 105
1 <= beans[i] <= 105
class Solution(object):
def minimumRemoval(self, beans):
length = len(beans)
beans.sort()
print(beans)
max_ = 0
for x,y in enumerate(beans):
# print(x,y)
end = y*(length-x)
if end > max_:
max_ = end
return sum(beans) - max_
obj = Solution()
obj.minimumRemoval([4,1,6,5])
标准答案:
class Solution:
def minimumRemoval(self, beans: List[int]) -> int:
n = len(beans)
beans.sort()
total = sum(beans) # 豆子总数
res = total # 最少需要移除的豆子数
for i in range(n):
res = min(res, total - beans[i] * (n - i))
return res