题目描述
给你一组带编号的 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
解法
方法一：哈希表 + 枚举
我们用一个哈希表 $cnt$ 统计数组 $nums$ 中每个数字出现的次数，我们记数字次数的最小值为 $k$，那么我们可以在 $[k,..1]$ 的范围内枚举分组的大小。由于每个组的大小差值不超过 $1$，那么分组大小为 $k$ 或 $k+1$。
对于当前枚举到的分组大小 $k$，我们遍历哈希表中的每个次数 $v$，如果 $\lfloor \frac{v}{k} \rfloor < v \bmod k$，那么说明无法将这个次数 $v$ 分成 $k$ 个或 $k+1$ 个数值相同的组，因此我们可以直接跳过这个分组大小 $k$。否则，说明可以分组，我们只需要尽可能分出最多的分组大小 $k+1$，即可保证得到最小的分组数，因此我们可以将 $v$ 个数分成 $\lceil \frac{v}{k+1} \rceil$ 组，累加到当前枚举的答案中。由于我们是按照 $k$ 从大到小枚举的，因此只要找到了一个合法的分组方案，那么一定是最优的。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def minGroupsForValidAssignment(self, nums: List[int]) -> int:
cnt = Counter(nums)
for k in range(min(cnt.values()), 0, -1):
ans = 0
for v in cnt.values():
if v // k < v % k:
ans = 0
break
ans += (v + k) // (k + 1)
if ans:
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | class Solution {
public int minGroupsForValidAssignment(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) {
cnt.merge(x, 1, Integer::sum);
}
int k = nums.length;
for (int v : cnt.values()) {
k = Math.min(k, v);
}
for (;; --k) {
int ans = 0;
for (int v : cnt.values()) {
if (v / k < v % k) {
ans = 0;
break;
}
ans += (v + k) / (k + 1);
}
if (ans > 0) {
return ans;
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
public:
int minGroupsForValidAssignment(vector<int>& nums) {
unordered_map<int, int> cnt;
for (int x : nums) {
cnt[x]++;
}
int k = 1e9;
for (auto& [_, v] : cnt) {
ans = min(ans, v);
}
for (;; --k) {
int ans = 0;
for (auto& [_, v] : cnt) {
if (v / k < v % k) {
ans = 0;
break;
}
ans += (v + k) / (k + 1);
}
if (ans) {
return ans;
}
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | func minGroupsForValidAssignment(nums []int) int {
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
k := len(nums)
for _, v := range cnt {
k = min(k, v)
}
for ; ; k-- {
ans := 0
for _, v := range cnt {
if v/k < v%k {
ans = 0
break
}
ans += (v + k) / (k + 1)
}
if ans > 0 {
return ans
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | function minGroupsForValidAssignment(nums: number[]): number {
const cnt: Map<number, number> = new Map();
for (const x of nums) {
cnt.set(x, (cnt.get(x) || 0) + 1);
}
for (let k = Math.min(...cnt.values()); ; --k) {
let ans = 0;
for (const [_, v] of cnt) {
if (((v / k) | 0) < v % k) {
ans = 0;
break;
}
ans += Math.ceil(v / (k + 1));
}
if (ans) {
return ans;
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | use std::collections::HashMap;
impl Solution {
pub fn min_groups_for_valid_assignment(nums: Vec<i32>) -> i32 {
let mut cnt: HashMap<i32, i32> = HashMap::new();
for x in nums.iter() {
let count = cnt.entry(*x).or_insert(0);
*count += 1;
}
let mut k = i32::MAX;
for &v in cnt.values() {
k = k.min(v);
}
for k in (1..=k).rev() {
let mut ans = 0;
for &v in cnt.values() {
if v / k < v % k {
ans = 0;
break;
}
ans += (v + k) / (k + 1);
}
if ans > 0 {
return ans;
}
}
0
}
}
|