题目描述
思路解析
一句话答案：LeetCode 1282 用户分组：每人指定所在组的大小，按大小分桶——扫一趟把人丢进对应编号的桶，桶一满就当作一组发出、清空复用，写同一个数的人可互换所以随到随分，时间 O(n)。
每个人指定所在组的大小，怎么分
给一个数组 groupSizes，位置 i 上的数就是第 i 个人要求的组大小——他必须待在一个正好这么多人的组里。要把 0 到 n−1 全部人分完，每人恰好进一组，且每组的实际人数等于组里每个人纸条上写的那个数。题面示例 groupSizes=[3,3,3,3,3,1,3]，一种合法答案是 [[0,1,2],[5],[3,4,6]]：三个写 3 的凑一组，写 1 的自己单独成组。答案不唯一，写同一个数的人谁跟谁一组都行，题目也保证至少存在一种分法。
要不要把所有分组方式都试一遍
一上来容易担心分组得试各种搭配、凑不齐还要回头换人，那就落进了回溯的指数级枚举，即走不通就退回来重排。但这里有个省事的点被漏掉了：一个人进多大的组是写死的、和别人无关；而写同一个数的人，彼此完全可以互换，谁配谁都合法。既然如此，凑够人就能立刻锁定一组，用不着比较，也用不着反悔。
按组大小分桶，凑满就发出去
给每种组大小准备一个桶，桶的编号就是它要凑的人数。从头扫一遍，读到一个人就看他纸条写几，把他丢进对应编号的桶。哪个桶里的人数一旦等于它的编号，这一桶就正好是一个满员的组，当场打包进答案，随后把桶倒空。倒空的桶不作废，后面再遇到写同样数字的人，又从空桶重新攒起。整趟扫下来随到随分，既不排序也不回溯。
发完组为什么要连着倒空桶
发组和倒空必须是连着的一步。要是只把满桶的名单记进答案、却忘了清桶，下一个写同样数字的人还会接着往里塞，桶越攒越多，发出去的组人数就超了。倒空之后这只桶继续服役：同一个编号的桶，一整趟里会反复攒满、反复发货。还有个换语言才冒头的坑——Java、C++ 里若把桶这只列表直接塞进答案再清空，答案里存的是同一只列表的引用，清桶会把已发出去的那组一起抹掉；得先拷一份进答案，再清原桶。
把七人依次塞进桶
照着 groupSizes=[3,3,3,3,3,1,3] 走。第 0、1 个人都写 3，进 3 号桶，桶里先 1 人、再 2 人，还没满。第 2 个人又写 3，进去凑到 3 人，正好等于桶号，打包出 [0,1,2]，3 号桶倒空。第 3、4 个人写 3，再进 3 号桶，攒到 2 人。第 5 个人写 1，进 1 号桶，一进就满员，发出 [5]，1 号桶倒空。第 6 个人写 3，进那只刚攒了 2 人的 3 号桶，凑到 3 人，发出 [3,4,6]。七个人扫完，所有桶都空，答案 [[0,1,2],[5],[3,4,6]]，三组正好覆盖七人。
扫一趟的开销，还有几个边界
从头到尾只扫一趟，每个人做一次入桶、一次满没满的判断，都是常数；满桶时把整组搬进答案，所有搬运合起来也不过是每人各搬一次，时间 O(n)。空间上，待成组的人加上已发出的组，峰值就是全部 n 个人各占一格，是 O(n)。边界上，写 1 的人一进桶就满、立刻单独成组；全体都写 1 时，每人各成一组、答案有 n 个单人组。题目保证有合法解，意味着写每个数 s 的人数一定是 s 的整数倍，所以扫到最后每只桶都恰好清空，不会剩下半桶凑不齐的人。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这条主线:按纸条数字入桶、桶满即发组、发完清桶继续攒。下面每一帧都在套这三个动作。
准备 · 看清舞台：上面这排格子,位置 i 就是第 i 个人,格子里写的数就是他要求的组大小。右边一开始没有桶,扫到谁、需要几号桶,就现开一个。下面从位置 0 开始,一个人一个人地处理。
准备 · 先扫一眼需求：先粗看一遍纸条:位置 0 到 4 还有位置 6 都写着 3,只有位置 5 写的是 1。写 3 的有六个人,正好能分成两组三人;写 1 的就一个人,自己成一组。心里有数了,正式开桶。
读 · 第 0 个人 需要 3 人组：轮到第 0 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
入桶 · 3 号桶 现有 1 人：把第 0 个人丢进 3 号桶,桶里现在有 1 个人,离攒满 3 个还差 2 个,继续往下扫。
读 · 第 1 个人 需要 3 人组：轮到第 1 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
入桶 · 3 号桶 现有 2 人：把第 1 个人丢进 3 号桶,桶里现在有 2 个人,离攒满 3 个还差 1 个,继续往下扫。
读 · 第 2 个人 需要 3 人组：轮到第 2 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
入桶 · 3 号桶 现有 3 人：把第 2 个人丢进 3 号桶,桶里正好攒到 3 个人,达标了!下一步就把这一桶打包发出去。
发组 · [0,1,2]：3 号桶攒够 3 个人了,把整桶 [0,1,2] 当作完整的一组发出去,然后把 3 号桶倒空。注意桶并没有作废,后面再有写 3 的人,还会从空桶重新攒起。
读 · 第 3 个人 需要 3 人组：轮到第 3 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
入桶 · 3 号桶 现有 1 人：把第 3 个人丢进 3 号桶,桶里现在有 1 个人,离攒满 3 个还差 2 个,继续往下扫。
读 · 第 4 个人 需要 3 人组：轮到第 4 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
入桶 · 3 号桶 现有 2 人：把第 4 个人丢进 3 号桶,桶里现在有 2 个人,离攒满 3 个还差 1 个,继续往下扫。
读 · 第 5 个人 需要 1 人组：轮到第 5 个人,他的纸条写着 1,意思是「我得待在一个 1 人的组里」。那就把他往 1 号桶里放。
入桶 · 1 号桶 现有 1 人：把第 5 个人丢进 1 号桶,桶里正好攒到 1 个人,达标了!下一步就把这一桶打包发出去。
发组 · [5]：1 号桶攒够 1 个人了,把整桶 [5] 当作完整的一组发出去,然后把 1 号桶倒空。注意桶并没有作废,后面再有写 1 的人,还会从空桶重新攒起。
读 · 第 6 个人 需要 3 人组：轮到第 6 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
入桶 · 3 号桶 现有 3 人：把第 6 个人丢进 3 号桶,桶里正好攒到 3 个人,达标了!下一步就把这一桶打包发出去。
发组 · [3,4,6]：3 号桶攒够 3 个人了,把整桶 [3,4,6] 当作完整的一组发出去,然后把 3 号桶倒空。注意桶并没有作废,后面再有写 3 的人,还会从空桶重新攒起。
收束 · 答案成形：七个人一个不落都进了组,所有桶也恰好都空了。回看一下:[0,1,2] 和 [3,4,6] 都是三人组,对应那六个写 3 的人;[5] 是单人组,对应写 1 的那位。答案 [0,1,2]、[5]、[3,4,6] 成立。
校验 · 人数对得上：再做个数量校验:三组人数 3 加 1 加 3 等于 7,正好就是总人数,而且每个编号只在一组里出现一次。每个人所在组的大小也都和他纸条写的一致,这个分法稳稳合法。
边界先想清:单人 size 1 立刻成组、两人凑满一组、全写 1 时各自成组。
面试重点:大小独立且同大小可互换所以贪心一趟过、Java 和 C++ 清桶前要拷贝、只要数量时可只记计数省空间。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]: buckets = defaultdict(list) ans = [] for i, size in enumerate(groupSizes): buckets[size].append(i) if len(buckets[size]) == size: ans.append(buckets[size]) buckets[size] = [] return ans复杂度
- 时间：O(n)，n 为人数。从头到尾扫一趟,每个人做一次入桶、一次「是否满」判断,都是常数操作;满桶时把整组搬进答案,所有搬运加起来也只是把每个人各搬一次,总量仍是 O(n)
- 空间：O(n)，按峰值算:所有桶里待成组的人加上已发出的组,合计最多就是全部 n 个人各占一格,所以是 O(n)。哈希表本身键的种类不超过 n,也在 O(n) 内
易错点
面试追问把动画讲成自己的话
追问这题为什么能一趟扫描搞定,不用回溯也不用排序?
追问Java 和 C++ 为什么要先把桶拷贝一份再清空?
追问如果只想要分组数量,而不要具体名单,做法会更省吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
数组大小减半
LeetCode 1338 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题