LeetCode 1282. 用户分组

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 亚马逊
标签
数组 哈希表 贪心
目录

题目描述

✅ 1282. 用户分组

题意分析

groupSizes[i] 表示第 i 个人所在的组恰好有多少人。要求把所有人划分成若干组，使每个人的实际组大小等于他被标注的那个数。返回任意一种可行划分即可。

「返回任意一种」这句话价值极高——它意味着不需要搜索、不需要判优、也不存在无解情况。题目保证至少存在一个解，我们只要产出一个合法的就行。

关键推论：标注值不同的人绝对不可能在同一组。因为同组的每个人看到的组大小是同一个数，如果两人标注不同，其中至少一个人的标注会与实际组大小矛盾。所以整个问题按标注值天然被切成互不干扰的若干独立子问题。

再看每个子问题：标注为 k 的所有人必须被分成若干个大小恰好为 k 的组。这也说明标注为 k 的人数一定是 k 的倍数（题目保证有解，隐含了这一点），而且组内具体是哪 k 个人完全无所谓——任意 k 个都行。

规模：人数上限 500，groupSizes[i] 在 $[1, n]$ 之间。规模很小，但正确解本身就是线性的，不需要为规模做任何妥协。

边界：所有人标注都是 1（每人自成一组）、所有人标注都是 n（全体一组）、同一个标注值对应多组、标注值稀疏分布。

解法：哈希表分桶

核心思路

标注为不同组大小的人不可能在同一组，因此按 groupSizes[i] 分桶即可。对大小为 k 的桶，每收集到 k 个下标，就立刻把它作为一个完整组输出，并从哈希表中移除这个桶；之后同样大小的人会创建新桶。

不变量：处理完任意前缀后，每个哈希桶只保存尚未分组的人，桶键为 k 时人数严格小于 k；结果中的每一组已封闭，组内所有人的标注都等于该组人数。

正确性说明：新用户只进入与自己标注相同的桶。桶未满时不变量直接保持；恰好满 k 人时输出并移除桶，这 k 人各出现一次且不会再被修改。题目保证输入有解，因此遍历结束不会留下未满桶，所有用户都恰好属于一个合法组。

这里无需搜索“最佳分法”：同一桶内成员可以任意组合，先到先成组不会影响剩余人数仍可按相同大小分组。

解题步骤

  1. 建立“组大小到当前未满组”的哈希表，以及结果列表。
  2. 遍历用户下标 i，把它加入键为 groupSizes[i] 的桶。
  3. 若桶人数达到其目标大小，将桶对象加入结果，并从哈希表移除该键。
  4. 遍历结束后返回结果。

对 [3,3,3,3,3,1,3]，前三个下标组成 [0,1,2]；下标 5 立即形成单人组 [5]；剩余标注为 3 的下标组成 [3,4,6]。不同组的输出顺序不影响合法性。

移除已满桶很重要：结果直接持有这个列表，后续同大小用户必须使用新列表，不能继续修改已经输出的组。

代码实现

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        Map<Integer, List<Integer>> buckets = new HashMap<>();
        List<List<Integer>> answer = new ArrayList<>();

        for (int person = 0; person < groupSizes.length; person++) {
            int size = groupSizes[person];
            List<Integer> group =
                    buckets.computeIfAbsent(size, key -> new ArrayList<>());
            group.add(person);

            if (group.size() == size) {
                answer.add(group);
                buckets.remove(size);
            }
        }
        return answer;
    }
}

func groupThePeople(groupSizes []int) [][]int {
	buckets := make(map[int][]int)
	answer := make([][]int, 0)

	for person, size := range groupSizes {
		group := append(buckets[size], person)
		if len(group) == size {
			answer = append(answer, group)
			delete(buckets, size)
		} else {
			buckets[size] = group
		}
	}
	return answer
}

复杂度分析

设用户数为 n。

  • 时间复杂度： 平均 $O(n)$。每个用户只进行一次哈希访问和一次追加。
  • 空间复杂度： $O(n)$，包含结果中的全部下标；不计输出时，未满桶合计最多保存 n 个下标。

关键点总结

  • 组大小是天然分桶键，不同键之间完全独立。
  • “返回任意合法答案”意味着同桶成员可以按到达顺序直接成组，无需回溯或排序。
  • 未满桶保存待分配用户，满桶立即封闭并与哈希表脱离，这是算法的不变量。
  • Java 直接保存已满列表、Go 直接保存已满切片都安全，因为后续会为该大小创建新的容器。

易错点总结

  • 已满后继续复用同一容器： 后续追加会修改结果中已经输出的组；应移除桶并让下一批创建新容器。
  • 用赋值覆盖桶而不是追加： 同一大小永远攒不满，只会保留最后一个用户。
  • 把标注值而非用户下标加入结果： 题目要求返回人员编号。
  • 只允许每个大小产生一组： [3,3,3,3,3,1,3] 中大小 3 必须产生两组。
  • 末尾自行输出未满桶： 这会生成尺寸不合法的组；题目保证有解，正确流程结束时所有桶都为空。

相似题目

题目 难度 考察点
49. 字母异位词分组 中等 分桶键需要自己构造（排序后的串或字符频次签名）
621. 任务调度器 中等 同样按类别聚合，但要按最大频次推导排布长度而非直接切块
767. 重构字符串 中等 分组后还要交错排列，需先用频次上界判定是否有解
1013. 将数组分成和相等的三个部分 简单 切分依据是累计和而非计数，攒满即切的思路完全一致