题目描述
思路解析动画文字版
记牢这条主线:按纸条数字入桶、桶满即发组、发完清桶继续攒。下面每一帧都在套这三个动作。
准备 · 看清舞台：上面这排格子,位置 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题