2171.拿出最少数目的魔法豆

链接：2171.拿出最少数目的魔法豆
难度：Medium
标签：贪心、数组、枚举、前缀和、排序
简介：给定一个 正整数 数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少还有一颗 魔法豆的袋子）魔法豆的数目 相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。请返回你需要拿出魔法豆的 最少数目。

题解 1 - python

• 编辑时间：2024-01-18
• 执行用时：372ms
• 内存消耗：39.59MB
• 编程语言：python
• 解法介绍：遍历。

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        counter = list(Counter(beans).items())
        counter.sort(reverse = True)
        ans = nsum = sum(beans)
        ncnt = 0
        prev_num = -1
        for num, cnt in counter:
            if prev_num != -1: nsum += ncnt * (prev_num - num)
            nsum -= num * cnt
            prev_num = num
            ncnt += cnt
            ans = min(ans, nsum)
        return ans