What is the time complexity of this problem?

The time complexity is O(n) for counting frequencies using a hash map, where n is the number of balls.

What should I consider when determining the number of boxes?

The number of boxes is determined by the highest frequency of any ball. Ensure that the distribution between boxes remains as balanced as possible.

What is the greedy approach used in this problem?

The greedy approach ensures that the distribution of balls into boxes minimizes the number of boxes by filling boxes to balance their sizes while adhering to the constraints.

How does the frequency of balls impact the solution?

The frequency of balls dictates the minimum number of boxes required, as the most frequent ball determines the least number of boxes needed to avoid exceeding the maximum size difference.

Can the approach change if there are fewer boxes than balls?

Yes, in that case, you would need to adjust your strategy, possibly considering constraints on the number of available boxes or adapting to a different problem variant.

#2910

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

合法分组的最少组数

给你一组带编号的 balls 并要求将它们分类到盒子里，以便均衡地分配。你必须遵守两条规则：同一个盒子里的球必须具有相同的编号。但是，如果你有多个相同编号的球，你可以把它们放在不同的盒子里。最大的盒子只能比最小的盒子多一个球。返回遵循上述规则排列这些球所需要的盒子的最小数目。示例 1：输入…

数组哈希表贪心

题目描述

给你一组带编号的 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 <= 10⁵
1 <= balls[i] <= 10⁹

lightbulb

解题思路

方法一：哈希表 + 枚举

我们用一个哈希表 $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

13

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ensure the candidate correctly identifies the use of a hash map for frequency calculation.
question_mark
Look for understanding of greedy algorithms and the significance of the most frequent number.
question_mark
Evaluate how the candidate balances the box distribution to avoid exceeding the maximum allowed size difference.

warning

常见陷阱

外企场景

error
Candidates may fail to consider edge cases where the ball numbers are very skewed in frequency.
error
Misunderstanding the problem can lead candidates to overcomplicate the solution or underutilize hash maps.
error
Failing to account for the greedy approach could lead to inefficient solutions or incorrect box counts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the balls are not sorted?
arrow_right_alt
How does the solution change if balls must be grouped into fixed-size boxes?
arrow_right_alt
How would the approach differ if the maximum allowed box size was reduced?

help

常见问题

外企场景

继续练习

#2897 对数组执行操作使平方和最大 #2870 使数组为空的最少操作次数 #2856 删除数对后的最小数组长度