LEETCODE 1282. Group the People Given the Group Size They Belong To 解题思路分析

题目大意：

用户分组

有 n 位用户参加活动，他们的 ID 从 0 到 n – 1，每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 groupSizes，其中包含每位用户所处的用户组的大小，请你返回用户分组情况（存在的用户组以及每个组中用户的 ID）。

你可以任何顺序返回解决方案，ID 的顺序也不受限制。此外，题目给出的数据保证至少存在一种解决方案。

示例 1：

输入：groupSizes = [3,3,3,3,3,1,3]
输出：[[5],[0,1,2],[3,4,6]]
解释： 
 其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。

示例 2：

输入：groupSizes = [2,1,3,3,3,2]
输出：[[1],[0,5],[2,3,4]]

提示：

• groupSizes.length == n
• 1 <= n <= 500
• 1 <= groupSizes[i] <= n

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1282

解题思路分析：

这道题的算法并不复杂，分组时只需看当前人所在的组的人数即可。我们定义一个HashMap，key为该组的人数，value为该组的用户列表，如果HashMap中不存在该人数的组，我们就新建一个，并将当前用户存入该组，如果Map中已经存在该组，直接将当前用户分入该组即可。分配完用户之后，查看该组的人数是否已满，如果满了，就将该组的用户列表存入返回结果，并从HashMap中删除该组。循环完所有用户之后，分组也会随之完成。

实现代码：

public List<List<Integer>> groupThePeople(int[] groupSizes) {
    List<List<Integer>> res=new ArrayList<>(); // 返回结果
    Map<Integer, List<Integer>> temp = new HashMap<>(); // 分组用Map
    for(int i=0;i<groupSizes.length;i++){ // 循环所有用户
        // 利用当前用户所在组的人数，得到该组成员列表，没有就新建一个
        List<Integer> list
          =temp.getOrDefault(groupSizes[i],new ArrayList<>());
        // 将当前用户存入该组
        list.add(i);
        // 如果当前组人已满
        if(list.size()==groupSizes[i]){
            res.add(list); // 将当前组存入返回结果
            temp.remove(groupSizes[i]); // 从map中删除该组
        }else{
            // 如果当前组人每满，更新map中该组成员列表
            temp.put(groupSizes[i],list);
        }
    }
    return res;
}

本题解法执行时间为5ms。

Runtime: 5 ms, faster than 100.00% of Java online submissions for Group the People Given the Group Size They Belong To.

Memory Usage: 38.5 MB, less than 100.00% of Java online submissions for Group the People Given the Group Size They Belong To.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1282-group-the-people-given-the-group-size-they-belong-to-解题思路分析/