拿出最少数目的魔法豆

难度: Medium

给定一个 正整数 数组 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 <= 10⁵
1 <= beans[i] <= 10⁵

Submission

运行时间: 172 ms

内存: 28.0 MB

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        total = sum(beans)
        beans.sort()
        min_beans = 1e20
        n = len(beans)
        last_val = -1
        for index, val in enumerate(beans):
            if val == last_val:
                continue
            cur_min = total - (n - index) * val
            if cur_min < min_beans:
                min_beans = cur_min
            last_val = val
        return min_beans

Explain

这个解决方案首先计算了beans数组中魔法豆的总数。然后，它对beans数组进行排序以方便后续操作。接着，遍历排序后的beans数组，计算如果所有非空袋子的魔法豆数为当前值时，需要移除的魔法豆总数。这个计算通过从总数中减去当前值乘以剩余袋子的数量来实现。算法记录下遍历过程中的最小移除数量。因为数组是排序后的，所以它确保只计算每个不同的豆子数量一次，避免重复计算。最后，返回记录的最小移除数量。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        total = sum(beans)  # 计算魔法豆的总数
        beans.sort()  # 对数组进行排序
        min_beans = 1e20  # 初始化最小移除数量为一个非常大的数
        n = len(beans)  # 获取豆子袋子的数量
        last_val = -1  # 用来记录上一个处理的豆子数量，避免重复计算
        for index, val in enumerate(beans):
            if val == last_val:  # 如果当前值与上一个值相同，跳过以减少重复计算
                continue
            cur_min = total - (n - index) * val  # 计算当前值作为目标时，需要移除的豆子数
            if cur_min < min_beans:  # 更新最小移除数量
                min_beans = cur_min
            last_val = val  # 更新上一个值
        return min_beans  # 返回最小移除数量

Explore

在算法中，通过对 beans 数组进行排序，并遍历每个不同的豆子数作为最终目标的可能性来确定。排序后，对于数组中的每个元素（豆子数），算法考虑如果所有非空袋子都有相同的豆子数（即当前遍历到的豆子数），需要移除的豆子总数。通过这种方式，可以确保考虑每种可能的豆子数，并找到导致最小移除总数的最优豆子数。

这种计算逻辑是基于将所有非空袋子的豆子数调整到当前考虑的豆子数（当前值）。通过计算`当前值乘以剩余袋子的数量`，我们得到如果将所有非空袋子调整到当前值所应有的总豆子数。将这个数从总豆子数中减去，得到的就是为了达到这个状态需要移除的豆子总数。这样的计算可以帮助我们找到移除豆子数最少的情况，即使所有非空袋子的豆子数一致。

检查`val == last_val`并跳过这些值的目的是为了避免重复计算。因为数组已经排序，相同的豆子数量会连续出现。如果不跳过重复的豆子数量，那么对于相同的豆子数，算法会重复计算相同的移除数量，这是不必要的。通过跳过已经计算过的豆子数量，可以提高算法的效率和执行速度。

在算法执行过程中，`min_beans`是在找到更小的移除豆子总数时更新的。具体来说，每次计算得到当前豆子数作为目标时需要移除的豆子总数后，都会与当前记录的`min_beans`（最小移除数量）进行比较。如果当前计算的移除数量小于`min_beans`，则更新`min_beans`为当前计算的值。这确保了算法能够持续跟踪并返回遍历过程中遇到的最小移除数量。