[LeetCode] 1282. Group the People Given the Group Size They Belong To

There are n people whose IDs go from 0 to n - 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people's IDs each group includes.

You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

Constraints:

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

用户分组。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-the-people-given-the-group-size-they-belong-to
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是用hashmap，key存某个分组的大小，value是一个list，list里面存的是每个人的index。举个例子，比如第一个例子，当我遇到第一个3的时候，我知道index为0的人是被分到了一个三人组；同理，index为1，2，3，4，6的人也都被分到了一个三人组，但是index为5的那个人是自己一个人一组的。遍历input，当遇到同样的groupSizes[i]的时候，就将i放入hashmap对应的key的list中。同时注意，每次加入之后记得看一下当前list的大小是否等于当前的key了，意思是看一下当前list里面的人数是否已经达到groupSizes[i]，若达到了，则说明有一个分组已经确定，可以加入结果集，同时记得将map里这个entry整个删掉，否则会报错。举个例子，还是第一个例子，当你遍历到前三个3的时候，其实你已经确定好了第一个分组，如果此时你不删除这个分组，那么后面的3也会被加入map里key为3的那个entry里面，导致结果错误。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public List<List<Integer>> groupThePeople(int[] groupSizes) {
 3         Map<Integer, List<Integer>> map = new HashMap<>();
 4         List<List<Integer>> res = new ArrayList<>();
 5         for (int i = 0; i < groupSizes.length; i++) {
 6             if (!map.containsKey(groupSizes[i])) {
 7                 map.put(groupSizes[i], new ArrayList<>());
 8             }
 9             List<Integer> cur = map.get(groupSizes[i]);
10             cur.add(i);
11             if (cur.size() == groupSizes[i]) {
12                 res.add(cur);
13                 map.remove(groupSizes[i]);
14             }
15         }
16         return res;
17     }
18 }

JavaScript实现

 1 /**
 2  * @param {number[]} groupSizes
 3  * @return {number[][]}
 4  */
 5 var groupThePeople = function(groupSizes) {
 6     let res = [];
 7     let map = new Map();
 8     for (let i = 0; i < groupSizes.length; i++) {
 9         if (!map.has(groupSizes[i])) {
10             map.set(groupSizes[i], []);
11         }
12         let cur = map.get(groupSizes[i]);
13         cur.push(i);
14         if (cur.length == groupSizes[i]) {
15             res.push(cur);
16             map.delete(groupSizes[i]);
17         }
18     }
19     return res;
20 };

LeetCode 题目总结

[LeetCode] 1282. Group the People Given the Group Size They Belong To

推荐阅读