LeetCode 1282中等贪心 · 排序
用户分组 图解题解
这道题到底在问什么
给定数组 groupSizes,groupSizes[i] 表示第 i 个人要求所在组的人数。把所有人分成若干组,使每个人 i 所在组的大小恰好等于 groupSizes[i]。每人恰好出现在一组里。有多个答案时返回任意一个,题目保证至少有一个合法分法。
- 输入
- groupSizes=[3,3,3,3,3,1,3]
- 输出
- [[0,1,2],[5],[3,4,6]]
- 输入
- groupSizes=[2,1,3,3,3,2]
- 输出
- [[1],[2,3,4],[0,5]]
最优解：一步一步想明白
- 3记牢这条主线:按纸条数字入桶、桶满即发组、发完清桶继续攒。下面每一帧都在套这三个动作。
- 4上面这排格子,位置 i 就是第 i 个人,格子里写的数就是他要求的组大小。右边一开始没有桶,扫到谁、需要几号桶,就现开一个。下面从位置 0 开始,一个人一个人地处理。
- 5先粗看一遍纸条:位置 0 到 4 还有位置 6 都写着 3,只有位置 5 写的是 1。写 3 的有六个人,正好能分成两组三人;写 1 的就一个人,自己成一组。心里有数了,正式开桶。
- 6轮到第 0 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
- 7把第 0 个人丢进 3 号桶,桶里现在有 1 个人,离攒满 3 个还差 2 个,继续往下扫。
- 8轮到第 1 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
- 9把第 1 个人丢进 3 号桶,桶里现在有 2 个人,离攒满 3 个还差 1 个,继续往下扫。
- 10轮到第 2 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
- 11把第 2 个人丢进 3 号桶,桶里正好攒到 3 个人,达标了!下一步就把这一桶打包发出去。
- 123 号桶攒够 3 个人了,把整桶 [0,1,2] 当作完整的一组发出去,然后把 3 号桶倒空。注意桶并没有作废,后面再有写 3 的人,还会从空桶重新攒起。
- 13轮到第 3 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
- 14把第 3 个人丢进 3 号桶,桶里现在有 1 个人,离攒满 3 个还差 2 个,继续往下扫。
- 15轮到第 4 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
- 16把第 4 个人丢进 3 号桶,桶里现在有 2 个人,离攒满 3 个还差 1 个,继续往下扫。
- 17轮到第 5 个人,他的纸条写着 1,意思是「我得待在一个 1 人的组里」。那就把他往 1 号桶里放。
- 18把第 5 个人丢进 1 号桶,桶里正好攒到 1 个人,达标了!下一步就把这一桶打包发出去。
- 191 号桶攒够 1 个人了,把整桶 [5] 当作完整的一组发出去,然后把 1 号桶倒空。注意桶并没有作废,后面再有写 1 的人,还会从空桶重新攒起。
- 20轮到第 6 个人,他的纸条写着 3,意思是「我得待在一个 3 人的组里」。那就把他往 3 号桶里放。
- 21把第 6 个人丢进 3 号桶,桶里正好攒到 3 个人,达标了!下一步就把这一桶打包发出去。
- 223 号桶攒够 3 个人了,把整桶 [3,4,6] 当作完整的一组发出去,然后把 3 号桶倒空。注意桶并没有作废,后面再有写 3 的人,还会从空桶重新攒起。
- 23七个人一个不落都进了组,所有桶也恰好都空了。回看一下:[0,1,2] 和 [3,4,6] 都是三人组,对应那六个写 3 的人;[5] 是单人组,对应写 1 的那位。答案 [0,1,2]、[5]、[3,4,6] 成立。
- 24再做个数量校验:三组人数 3 加 1 加 3 等于 7,正好就是总人数,而且每个编号只在一组里出现一次。每个人所在组的大小也都和他纸条写的一致,这个分法稳稳合法。
⚠️ 容易写错的地方
✗ 错：把同样写 3 的人硬塞进同一组、超过 3 个也不发
✓ 对：桶一满 3 人就立刻发组清桶
不及时发组,桶会越攒越多,组大小就超了;攒满即发才能保证每组恰好 size 人
✗ 错：Java / C++ 直接把桶对象塞进答案再 clear
✓ 对：先拷贝一份桶内容进答案,再 clear 原桶
答案里存的是同一个列表引用,清原桶会连答案里那组一起清空,组就丢了
✗ 错：以为发完组桶就没用了、不再复用
✓ 对：清空的桶继续攒下一组同大小的人
示例里 3 号桶攒满 [0,1,2] 发掉后,又重新攒出 [3,4,6],同一个桶要反复用
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
unordered_map<int, vector<int>> buckets;
vector<vector<int>> ans;
for (int i = 0; i < (int)groupSizes.size(); ++i) {
int size = groupSizes[i];
buckets[size].push_back(i);
if ((int)buckets[size].size() == size) {
ans.push_back(buckets[size]);
buckets[size].clear();
}
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public List<List<Integer>> groupThePeople(int[] groupSizes) {
Map<Integer, List<Integer>> buckets = new HashMap<>();
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < groupSizes.length; i++) {
int size = groupSizes[i];
buckets.computeIfAbsent(size, k -> new ArrayList<>()).add(i);
if (buckets.get(size).size() == size) {
ans.add(new ArrayList<>(buckets.get(size)));
buckets.get(size).clear();
}
}
return ans;
}
}复杂度
时间
O(n)
n 为人数。从头到尾扫一趟,每个人做一次入桶、一次「是否满」判断,都是常数操作;满桶时把整组搬进答案,所有搬运加起来也只是把每个人各搬一次,总量仍是 O(n)
空间
O(n)
按峰值算:所有桶里待成组的人加上已发出的组,合计最多就是全部 n 个人各占一格,所以是 O(n)。哈希表本身键的种类不超过 n,也在 O(n) 内
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 用户分组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么能一趟扫描搞定,不用回溯也不用排序?+
因为每个人要进多大的组是写死的、互相独立,而写同一个数的人完全可以互换。于是写 s 的人只要凑够 s 个就能立刻锁定一组,既不会影响别的大小,也不需要反悔。题目又保证有合法解,意味着每种大小 s 的人数一定是 s 的整数倍,桶最后必然都能恰好清空,所以一趟扫描、随到随分就够了。
Java 和 C++ 为什么要先把桶拷贝一份再清空?+
因为答案里存的是「指向那只列表的引用」。如果直接把桶引用塞进答案,再调用 clear 清桶,答案里那一组指向的是同一只列表,会被一起清空,组就没了。所以要先 new 一个新列表或按值拷贝一份进答案,再清原桶。Python 则是反着来,把旧列表挂进答案后,给桶换上一只全新的空列表,旧列表自然不受影响。
如果只想要分组数量,而不要具体名单,做法会更省吗?+
会更省空间。这时不必存每个人的下标,只需对每种大小 s 记一个当前计数,计数到 s 就把组数加一并把计数清零。空间从 O(n) 降到 O(不同大小的种数),时间仍是一趟 O(n)。当然本题要返回具体名单,所以还是得把人下标存进桶里。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 用户分组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。