LeetCode 1282. 用户分组

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

题目描述

✅ 1282. 用户分组

image-20260929080450978

image-20260929080451091

题意分析

每个人的编号是数组下标，groupSizes[i] 表示这个人所属组必须恰好有多少人。需要将所有人划分成若干组，使每人恰好出现一次，且所在组大小符合自己的要求。

相同大小可以组成多个组，成员不要求在原数组中连续，也不需要最小化组数。题目保证有解，可以返回任意满足条件的成员编号划分。

解法：哈希表分桶

核心思路

[!blue]

同一个组的实际人数只有一个确定值，因此组内所有人要求的大小必须相同。先按目标大小 k 将人分类，不同类别不能混组，也不会互相影响。

为每个 k 维护一个当前尚未凑满的成员列表，里面存人员下标。遍历时把当前人加入对应列表，达到 k 人就立刻收集为完整组，再为后续相同大小的人重新建组。

任取同类的 k 人成组都合法，因为他们没有除了组大小以外的成员限制。题目保证有解，要求大小为 k 的总人数必定是 k 的倍数；先取走任意完整的 k 人后，剩余人数仍能分成整组，因此凑满立即输出不会妨碍后面的分配。

满组交给结果后，从哈希表移除对应桶，让下一组使用新容器。不能把已经输出的列表清空后继续复用，否则答案里保存的同一对象或底层数组也可能被改变。每个人只在遍历自己的下标时加入一次，所以最终既不漏人也不重复。

解题步骤

  1. 创建从组大小到当前未满组的哈希表，以及结果列表。
  2. 逐个读取人员下标，按 groupSizes[person] 找到对应桶。
  3. 将人员下标加入桶；桶中人数达到要求大小时，将整组加入结果。
  4. 移除已经完成的桶，下一位同类成员到来时创建新组。
  5. 全部人员处理完后返回结果，有解保证不会留下需要强行补齐的未满组。

代码实现

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
}

复杂度分析

  • 时间复杂度：期望 $O(n)$，每个人只进行一次哈希分桶和加入操作，完整组无需重新扫描。
  • 空间复杂度：$O(n)$，未满桶最坏保存线性数量成员；返回结果总共还包含 n 个人员编号。

关键点总结

[!green]

  • 组大小决定独立类别，同类人数足够时任意成员组合都合法。
  • 桶键是目标大小，桶内容必须是原人员编号。
  • 满组立即移交结果，并为后续同类创建新容器。
  • 有解保证每类人数可整除组大小，在线凑组不会留下无法分配的人。

易错点总结

[!yellow]

  • 将 groupSizes 的数值作为成员编号输出，混淆要求大小与人员身份。
  • 每种大小只创建一个组，同类人数可能需要拆成多个相同大小的组。
  • 将目标大小不同的人混合，只能让部分成员满足要求。
  • 满组输出后清空并复用同一个列表或切片存储，已经返回的分组也可能被修改。
  • 人数尚未达到要求就将桶作为合法组输出，违反每个人所在组准确人数的条件。

相似题目

题目 难度 关联与区别
781. 森林中的兔子 中等 都按给出的组大小分桶，本题所有成员已知且数值就是组大小，兔子题回答的是其他同色数量且可能存在未出现成员。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/55496584
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！