难度: Medium
给你一组带编号的 balls 并要求将它们分类到盒子里，以便均衡地分配。你必须遵守两条规则：
返回遵循上述规则排列这些球所需要的盒子的最小数目。
示例 1：
输入：balls = [3,2,3,2,3] 输出：2 解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标： 我们可以如下排列 balls 到盒子里： - [3,3,3] - [2,2] 两个盒子之间的大小差没有超过 1。
示例 2：
输入：balls = [10,10,10,3,1,1] 输出：4 解释：我们可以如下排列 balls 到盒子里： - [10] - [10,10] - [3] - [1,1] 无法得到一个遵循上述规则且小于 4 盒的答案。例如，把所有三个编号为 10 的球都放在一个盒子里，就会打破盒子之间最大尺寸差异的规则。
提示：
1 <= balls.length <= 1051 <= balls[i] <= 109运行时间: 84 ms
内存: 38.7 MB
class Solution:
def minGroupsForValidAssignment(self, nums: List[int]) -> int:
# groups = dict()
# for num in nums:
# if num in groups:
# groups[num] += 1
# else:
# groups[num] = 1
G = list(Counter(nums).values())
G.sort()
m = G[0]
while(True):
flag = True
for g in G:
if g >= m*(m-1):
break
q, r = divmod(g, m)
if q < r:
flag = False
m = g//(q+1)
break
if flag:
break
res = 0
for g in G:
res += (g+m)//(m+1)
return res
此题解首先使用Counter来统计每种编号的球的数量，并将这些数量存储在列表G中。接着将G排序，目的是为了从最小的组开始处理。变量m初始化为G中的最小值，这代表着在迭代过程中尝试的最小盒子大小。接下来，代码通过一个循环不断调整m的值，以找到能满足条件的最小的m。内部循环检查每个g（即每种球的数量）是否能够被当前的m整除，如果不能，就调整m的值。最后，代码计算每种球按照最终确定的m分组后需要的盒子数，累加这些数得到最终结果。
时间复杂度: O(n + k log k)
空间复杂度: O(k)
class Solution:
def minGroupsForValidAssignment(self, nums: List[int]) -> int:
# 使用Counter统计每个编号球的数量
G = list(Counter(nums).values())
# 对数量进行排序
G.sort()
# 初始化m为最小的球的数量
m = G[0]
while(True):
flag = True
for g in G:
if g >= m*(m-1):
break
q, r = divmod(g, m)
if q < r:
flag = False
m = g//(q+1)
break
if flag:
break
res = 0
for g in G:
res += (g+m)//(m+1)
return res
选择G中的最小值作为m的初始值是基于算法效率和逻辑简化的考虑。实际上，最小值提供了一个可能的最小组大小的下界，从而确保我们从可能的最小分组开始探索，逐步增加组大小以找到合适的值。这种方法可以避免在不可能的小组大小上浪费计算资源，因为任何比G中最小数量还小的组大小都不可能合法地分配所有元素。
这个条件用于检查当前的分组大小m是否有可能导致非法的分组。如果某个g（即某种球的数量）大于或等于m*(m-1)，这意味着当前的分组大小m可能过小，不能有效地分配所有元素。这是一种优化检查，用于避免在不合适的m值上进行过多无效计算。这个条件帮助快速调整m至一个更可能的合理值，以减少不必要的迭代。
在这一步中，q代表整除结果，即每组m个元素可以分多少组，而r代表余数，即不能完整形成一组的剩余元素。如果q（完整组数）小于r（剩余元素数），这表明当前的m值过大，导致无法将所有元素均匀分配。因此，需要调整m的值，使得我们可以更合理地分配元素，至少确保每个组中元素的数量不会低于剩余元素的数量。
这个公式是在当前m值导致不能均匀分配的情况下调整m的尝试。通过将g除以(q+1)，我们试图找到一个新的组大小，这个大小可以使得每组至少分得q+1个元素，从而更加平均地分配剩余的元素。这种调整可以确保每组的元素数量尽可能地接近，避免某些组元素数量过多而其他组过少。这有助于找到一个更合理的m值，以达到更优的分组效果。