Medium

题目描述

给你一个编号球的集合，要求将它们排序到盒子中以实现近乎平衡的分布。你必须遵循两个规则：

  • 同一个盒子中的球必须有相同的值。但是，如果你有多个相同编号的球，你可以把它们放在不同的盒子中。
  • 最大的盒子最多只能比最小的盒子多一个球。

返回遵循这些规则排序这些球所需的最少盒子数。

示例 1：

输入：balls = [3,2,3,2,3]
输出：2
解释：
我们可以将球分组如下：
[3,3,3]
[2,2]
两个盒子的大小差异不超过一。

示例 2：

输入：balls = [10,10,10,3,1,1]
输出：4
解释：
我们可以将球分组如下：
[10]
[10,10]
[3]
[1,1]
在遵循规则的情况下，你不能使用少于四个盒子。例如，将所有三个编号为10的球放在一个盒子中会违反盒子之间最大大小差异的规则。

约束条件：

  • 1 <= balls.length <= 10^5
  • 1 <= balls[i] <= 10^9

解题思路

这道题的核心思路是贪心算法结合数学计算。

首先理解题意：我们需要将相同数字的球分到多个组中，使得所有组的大小差异不超过1，并且组数最少。

解题步骤：

  1. 统计频率：统计每个数字出现的次数

  2. 枚举组大小：由于组大小差异不超过1，我们可以枚举最小组大小x，那么组大小只能是x或x+1

  3. 计算最优分组：对于每个数字的频率f和组大小x，计算最少需要多少个组：

    • 设a = f / (x + 1)，b = f % (x + 1)
    • 如果b == 0，可以创建a个大小为x+1的组
    • 如果x - b <= a，可以创建a - (x - b)个大小为x+1的组和x - b + 1个大小为x的组，总计a+1个组
    • 否则无法满足条件

  4. 优化范围：x的取值范围是[1, min_frequency]，因为如果x大于某个数字的频率，就无法分组了

时间复杂度主要在枚举x和计算每个频率的分组数，通过数学公式可以高效计算。

代码实现

class Solution {
public:
    int minGroupsForValidAssignment(vector<int>& balls) {
        unordered_map<int, int> freq;
        for (int ball : balls) {
            freq[ball]++;
        }
        
        int minFreq = INT_MAX;
        for (auto& p : freq) {
            minFreq = min(minFreq, p.second);
        }
        
        int result = INT_MAX;
        
        for (int x = 1; x <= minFreq; x++) {
            int totalGroups = 0;
            bool valid = true;
            
            for (auto& p : freq) {
                int f = p.second;
                int a = f / (x + 1);
                int b = f % (x + 1);
                
                if (b == 0) {
                    totalGroups += a;
                } else if (x - b <= a) {
                    totalGroups += a + 1;
                } else {
                    valid = false;
                    break;
                }
            }
            
            if (valid) {
                result = min(result, totalGroups);
            }
        }
        
        return result;
    }
};

class Solution:
    def minGroupsForValidAssignment(self, balls: List[int]) -> int:
        from collections import Counter
        
        freq = Counter(balls)
        min_freq = min(freq.values())
        
        result = float('inf')
        
        for x in range(1, min_freq + 1):
            total_groups = 0
            valid = True
            
            for f in freq.values():
                a = f // (x + 1)
                b = f % (x + 1)
                
                if b == 0:
                    total_groups += a
                elif x - b <= a:
                    total_groups += a + 1
                else:
                    valid = False
                    break
            
            if valid:
                result = min(result, total_groups)
        
        return result

public class Solution {
    public int MinGroupsForValidAssignment(int[] balls) {
        var freq = new Dictionary<int, int>();
        foreach (int ball in balls) {
            freq[ball] = freq.GetValueOrDefault(ball, 0) + 1;
        }
        
        int minFreq = freq.Values.Min();
        int result = int.MaxValue;
        
        for (int x = 1; x <= minFreq; x++) {
            int totalGroups = 0;
            bool valid = true;
            
            foreach (int f in freq.Values) {
                int a = f / (x + 1);
                int b = f % (x + 1);
                
                if (b == 0) {
                    totalGroups += a;
                } else if (x - b <= a) {
                    totalGroups += a + 1;
                } else {
                    valid = false;
                    break;
                }
            }
            
            if (valid) {
                result = Math.Min(result, totalGroups);
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} balls
 * @return {number}
 */
var minGroupsForValidAssignment = function(balls) {
    const count = new Map();
    for (const ball of balls) {
        count.set(ball, (count.get(ball) || 0) + 1);
    }
    
    const frequencies = Array.from(count.values());
    const minFreq = Math.min(...frequencies);
    
    for (let k = minFreq; k >= 1; k--) {
        let totalGroups = 0;
        let valid = true;
        
        for (const freq of frequencies) {
            const fullGroups = Math.floor(freq / (k + 1));
            const remainder = freq % (k + 1);
            
            if (remainder === 0) {
                totalGroups += fullGroups;
            } else {
                const needed = k - remainder;
                if (needed <= fullGroups) {
                    totalGroups += fullGroups + 1;
                } else {
                    valid = false;
                    break;
                }
            }
        }
        
        if (valid) {
            return totalGroups;
        }
    }
    
    return frequencies.length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + k × m)，其中n是balls数组长度，k是最小频率，m是不同数字的个数
空间复杂度O(m)，用于存储频率统计，m是不同数字的个数