LeetCode 1282. 用户分组

Categories:

题目描述
思路分析
1. 解法一：哈希表分桶（推荐）
相似题目

题目描述

✅ 1282. 用户分组

思路分析

解法一：哈希表分桶（推荐）

核心思路：

用哈希表维护 size -> 当前收集的用户列表。

每加入一个用户到对应桶中，若人数达到 size 则输出该组并清空桶。

遍历结束后所有桶都会被清空。

复杂度分析：

时间复杂度：O(n)，其中 n 为用户数量。

空间复杂度：O(n)，存储分组缓存。

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>> res = new ArrayList<>();

        for (int i = 0; i < groupSizes.length; i++) {
            int size = groupSizes[i];
            List<Integer> list = buckets.computeIfAbsent(size, k -> new ArrayList<>());
            list.add(i);
            if (list.size() == size) {
                res.add(new ArrayList<>(list));
                list.clear();
            }
        }
        return res;
    }
}

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

    for i, size := range groupSizes {
        buckets[size] = append(buckets[size], i)
        if len(buckets[size]) == size {
            group := make([]int, size)
            copy(group, buckets[size])
            res = append(res, group)
            buckets[size] = buckets[size][:0]
        }
    }
    return res
}

相似题目

题目	难度	考察点
554. 砖墙	中等	哈希表
525. 连续数组	中等	哈希表
1. 两数之和	简单	哈希表
347. 前K个高频元素	中等	哈希表
451. 根据字符出现频率排序	中等	频次统计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/55496584