title
给你一个长度为 n 下标从 0 开始的整数数组 nums 。
我们想将下标进行分组，使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。
如果以下条件成立，我们说这个分组方案是合法的：
- 对于每个组
g，同一组内所有下标在nums中对应的数值都相等。 - 对于任意两个组
g1和g2，两个组中 下标数量 的 差值不超过1。
请你返回一个整数，表示得到一个合法分组方案的 最少 组数。
示例 1：
输入：nums = [3,2,3,2,3]
输出：2
解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：
组 1 -> [0,2,4]
组 2 -> [1,3]
所有下标都只属于一个组。
组 1 中，nums[0] == nums[2] == nums[4] ，所有下标对应的数值都相等。
组 2 中，nums[1] == nums[3] ，所有下标对应的数值都相等。
组 1 中下标数目为 3 ，组 2 中下标数目为 2 。
两者之差不超过 1 。
无法得到一个小于 2 组的答案，因为如果只有 1 组，组内所有下标对应的数值都要相等。
所以答案为 2 。
示例 2：
输入：nums = [10,10,10,3,1,1]
输出：4
解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：
组 1 -> [0]
组 2 -> [1,2]
组 3 -> [3]
组 4 -> [4,5]
分组方案满足题目要求的两个条件。
无法得到一个小于 4 组的答案。
所以答案为 4 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109
solution
将 s 个物品分成大小为 k 或 (k+1) 的的最少组数为：
- 情况1：首先尝试将 s 个物品分成大小是 (k+1) 的组，这样会分出 d1 = ⌊ (s/(k+1)) ⌋ 组，并且还剩下 r1 = s mod (k+1) 的物品。
- 若 r1 = 0，则直接分成 d1 组即可。
- 否则，如果 d1 + r1 ≥ k，则可以组成新的一组，总共可以分成 (d1+1) 组。
- 情况2：接下来尝试将 s 个物品分成大小是 k 的组，这样会分出 d2 = ⌊ (s/k) ⌋ 组，并且还剩下 r2 = s mod k 的物品。
- 因为 d2 组的大小都是最小值 k，所以不能再拿出物品和 r2 凑成新的一组，而是反过来要把 r2 塞进每一组里。由于 d2 组的每一组最多再加入一个物品。因此如果 r2 ≤ d2，那么就可以把所有物品分成 d2 组。
- 如果所有尝试都失败，那么这些物品不能被分成大小是 k 和 (k+1) 的组。
时间复杂度： O(n) as we can omit the sort.
设 nums 的长度为 n，且共有 t 种不同的数，那么最小值 min(s) 满足 min(s) ≤ t * n。这个不等式容易用反证法证明，如果 min(s) > t * n，由于每一组的大小都至少是 min(s)，那么所有组的总和就是 min(s) * t > min(s) * n，与一共只有 n 个数矛盾。
因此直接枚举 k ∈ [1, min(s)] 即可。复杂度为 O(min(s) * t) = O(tn) = O(n)。
class Solution:
def minGroupsForValidAssignment(self, nums: List[int]) -> int:
n = len(nums)
import collections
counter = collections.Counter()
for i, v in enumerate(nums):
counter[v] += 1
ans = len(counter)
d = sorted(counter.values())
if len(d) == 1:
return ans
elif len(d) == 2 and abs(d[0] - d[1]) <= 1:
return ans
# 把s个物品分成大小是k或(k+1)的组，最少要分成多少组
def min_groups(s, k):
divisor = s // (k + 1)
remainder = s % (k + 1)
cnt = 0
if remainder == 0:
cnt += divisor
elif divisor + remainder >= k:
cnt += divisor + 1
else:
divisor = s // k
remainder = s % k
# cnt == -1 表示无法分组
if remainder > divisor:
cnt = -1
else:
cnt += divisor
# print(s, k, cnt)
return cnt
mins = min(d)
ans = len(nums)
# print(mins)
for i in range(1, mins + 1):
cnt = 0
for v in d:
t = min_groups(v, i)
if t == -1:
cnt = -1
break
cnt += t
# print(i, cnt)
if cnt >= 0:
ans = min(ans, cnt)
return ans