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^5
  • 1 <= beans[i] <= 10^5

解题思路

解题思路

这道题的核心思想是枚举最终剩余的袋子数量，并计算对应的最小移除豆子数。

关键观察：

  1. 如果我们要让所有非空袋子的豆子数相等，那么最终的豆子数必须等于某个袋子的原始豆子数
  2. 当最终豆子数为 x 时，所有豆子数小于 x 的袋子都要清空，豆子数大于 x 的袋子要减少到 x

算法步骤：

  1. 首先对数组排序，这样可以方便地处理前缀和
  2. 枚举每个可能的最终豆子数（即数组中的每个值）
  3. 对于每个枚举值 beans[i]，计算移除的豆子数：
    • 前 i 个袋子全部清空：移除 prefixSum[i-1] 个豆子
    • 后面的袋子减少到 beans[i]：移除 suffixSum[i] - beans[i] * (n-i) 个豆子
  4. 取所有可能情况的最小值

时间复杂度优化： 可以用前缀和优化计算过程，避免重复计算。

代码实现

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        sort(beans.begin(), beans.end());
        int n = beans.size();
        
        long long total = 0;
        for (int bean : beans) {
            total += bean;
        }
        
        long long minRemoval = total;
        for (int i = 0; i < n; i++) {
            // 保留 (n - i) 个袋子，每个袋子有 beans[i] 个豆子
            long long keep = (long long)beans[i] * (n - i);
            minRemoval = min(minRemoval, total - keep);
        }
        
        return minRemoval;
    }
};

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        beans.sort()
        n = len(beans)
        total = sum(beans)
        
        min_removal = total
        for i in range(n):
            # 保留 (n - i) 个袋子，每个袋子有 beans[i] 个豆子
            keep = beans[i] * (n - i)
            min_removal = min(min_removal, total - keep)
        
        return min_removal

public class Solution {
    public long MinimumRemoval(int[] beans) {
        Array.Sort(beans);
        int n = beans.Length;
        
        long total = 0;
        foreach (int bean in beans) {
            total += bean;
        }
        
        long minRemoval = total;
        for (int i = 0; i < n; i++) {
            // 保留 (n - i) 个袋子，每个袋子有 beans[i] 个豆子
            long keep = (long)beans[i] * (n - i);
            minRemoval = Math.Min(minRemoval, total - keep);
        }
        
        return minRemoval;
    }
}

var minimumRemoval = function(beans) {
    beans.sort((a, b) => a - b);
    const n = beans.length;
    
    const total = beans.reduce((sum, bean) => sum + bean, 0);
    
    let minRemoval = total;
    for (let i = 0; i < n; i++) {
        // 保留 (n - i) 个袋子，每个袋子有 beans[i] 个豆子
        const keep = beans[i] * (n - i);
        minRemoval = Math.min(minRemoval, total - keep);
    }
    
    return minRemoval;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n)
空间复杂度O(1)

其中 n 是数组长度。时间复杂度主要由排序决定，空间复杂度为常数级别（不考虑排序的额外空间）。

相关题目