public List<List<Integer>> groupThePeople(int[] groupSizes) {}
时间: 2024-05-14 08:18:22 浏览: 10
这是一道 LeetCode 上的题目,题目编号是 1282。该题目的要求是将一群人按照不同的大小分组,使得每个组的大小都相同,并且每个人只能属于一个组。
具体来说,输入是一个整数数组 groupSizes,表示每个人所属的组的大小。例如,groupSizes[i]=3 表示第 i 个人属于一个大小为 3 的组。输出是一个二维整数数组,每个子数组表示一个分组,其中子数组的大小为该组的大小,子数组中的元素为该组中的人员编号。
以下是该问题的 Java 代码实现:
```java
public List<List<Integer>> groupThePeople(int[] groupSizes) {
List<List<Integer>> result = new ArrayList<>();
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < groupSizes.length; i++) {
int size = groupSizes[i];
if (!map.containsKey(size)) {
map.put(size, new ArrayList<>());
}
List<Integer> list = map.get(size);
list.add(i);
if (list.size() == size) {
result.add(new ArrayList<>(list));
list.clear();
}
}
return result;
}
```
算法思路:
1. 遍历整个数组,将每个人加入相应大小的组中。
2. 如果当前组的大小达到了要求,就将该组加入结果集中,并清空该组。
3. 最后返回结果集。
时间复杂度:O(n),其中 n 是数组的长度。遍历一次数组,每个人最多被遍历一次。
空间复杂度:O(n),使用了哈希表存储每个组的人员编号。