LeetCode 题解工作台
用户分组
有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的 唯一ID 。 给定一个整数数组 groupSizes ，其中 groupSizes[i] 是第 i 个人所在的组的大小。例如，如果 groupSizes[1] = 3 ，则第 1 个人必须位于大小为 3 的组中。 返回一…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用一个哈希表 来存放每个 都有哪些人。然后对每个 中的人划分为 等份，每一等份有 个人。 由于题目中的 范围较小，我们也可以直接创建一个大小为 的数组来存放数据，运行效率较高。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的唯一ID 。
给定一个整数数组 groupSizes ，其中 groupSizes[i] 是第 i 个人所在的组的大小。例如，如果 groupSizes[1] = 3 ，则第 1 个人必须位于大小为 3 的组中。
返回一个组列表，使每个人 i 都在一个大小为 groupSizes[i] 的组中。
每个人应该 恰好只 出现在 一个组 中，并且每个人必须在一个组中。如果有多个答案，返回其中 任何 一个。可以 保证 给定输入 至少有一个 有效的解。
示例 1：
输入：groupSizes = [3,3,3,3,3,1,3] 输出：[[5],[0,1,2],[3,4,6]] 解释： 第一组是 [5]，大小为 1，groupSizes[5] = 1。 第二组是 [0,1,2]，大小为 3，groupSizes[0] = groupSizes[1] = groupSizes[2] = 3。 第三组是 [3,4,6]，大小为 3，groupSizes[3] = groupSizes[4] = groupSizes[6] = 3。 其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
示例 2：
输入：groupSizes = [2,1,3,3,3,2] 输出：[[1],[0,5],[2,3,4]]
提示：
groupSizes.length == n1 <= n <= 5001 <= groupSizes[i] <= n
解题思路
方法一：哈希表或数组
我们用一个哈希表 来存放每个 都有哪些人。然后对每个 中的人划分为 等份，每一等份有 个人。
由于题目中的 范围较小，我们也可以直接创建一个大小为 的数组来存放数据，运行效率较高。
时间复杂度 ，空间复杂度 。其中 为 的长度。
class Solution:
def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
g = defaultdict(list)
for i, v in enumerate(groupSizes):
g[v].append(i)
return [v[j : j + i] for i, v in g.items() for j in range(0, len(v), i)]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) because we iterate through the groupSizes array once and build groups in linear time. Space complexity is O(N) for storing person IDs in the hash map and the final list of groups. |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Do you notice that grouping by size can be handled greedily with buckets?
- question_mark
Watch for off-by-one errors when splitting buckets into exact group sizes.
- question_mark
Consider whether a single pass can build all groups without revisiting elements.
常见陷阱
外企场景- error
Failing to create groups immediately when a bucket reaches its group size, causing leftover IDs.
- error
Mixing person IDs across different group size buckets, violating size constraints.
- error
Assuming a fixed group order instead of allowing any valid permutation.
进阶变体
外企场景- arrow_right_alt
Return groups in sorted order of their first member ID for consistent output.
- arrow_right_alt
Handle dynamic updates where new people join and require insertion into existing buckets.
- arrow_right_alt
Adapt to situations where group sizes may exceed current bucket length, requiring temporary holding lists.