用户分组 图解题解

每个人指定所在组的大小，怎么分

给一个数组 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 的整数倍，所以扫到最后每只桶都恰好清空，不会剩下半桶凑不齐的人。

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 ans

C++

#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;
    }
}