LeetCode 1282. 用户分组

题目描述

原题链接

有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的 唯一 ID。

给定一个整数数组 groupSizes，其中 groupSizes[i] 是第 i 个人所在的组的大小。例如，如果 groupSizes[1] = 3，则第 1 个人必须位于大小为 3 的组中。

返回一个组列表，使每个人 i 都在一个大小为 groupSizes[i] 的组中。

每个人应该 恰好只 出现在 一个组 中，并且每个人必须在一个组中。如果有多个答案，返回其中 任何 一个。可以 保证 给定输入 至少有一个 有效的解。

数据范围

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

样例1：

输入：groupSizes = [3,3,3,3,3,1,3]
输出：[[5],[0,1,2],[3,4,6]]
解释：
第一组是 [5]，大小为 1，groupSizes[5] = 1。
第二组是 [0,1,2]，大小为 3，groupSizes[0] = groupSizes[1] = groupSizes[2] = 3。
第三组是 [3,4,6]，大小为 3，groupSizes[3] = groupSizes[4] = groupSizes[6] = 3。
其他可能的解决方案有 [[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]]

---

算法

(哈希表) $O(n)$

1. 先对所有的数进行一个分类，建一个哈希表，key 为 组的人数，就是 num[i]的值，value 为一个 数组（表示数值等于 num[i] 的下标）数值相同的分在同一个组内。样例 1 举例：

3： 0， 1， 2， 3，4， 6
1： 5

2. 如果这个组的人数等于规定的人数，则当前哈希表里面的 value 为一个答案，输出该答案，然后清空当前 key 的那一个数组 ，重新插入数值。
3. 由于题目保证了至少有一个有效解，所以按照这个方法一定可以找到一个解。

时间复杂度

• 每个人的操作时间复杂度都是常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的空间存放哈希表以及答案，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        unordered_map<int, vector<int>> hash;
        vector<vector<int>> res;
        for (int i = 0; i < groupSizes.size(); i ++ )
        {
            int x = groupSizes[i];
            hash[x].push_back(i);
            if (hash[x].size() == x) {
                res.push_back(hash[x]);
                hash[x].clear();
            }
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Java 代码

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        Map<Integer, List<Integer>> hash = new HashMap<>();
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < groupSizes.length; i ++ )
        {
            int x = groupSizes[i];
            if (hash.get(x) == null) hash.put(x, new ArrayList<>());
            hash.get(x).add(i);
            if (hash.get(x).size() == x)
            {
                res.add(hash.get(x));
                hash.put(x, null);
            }
        } 
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Python3代码

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        hash = {}
        res = []
        for i in range(len(groupSizes)):
            x = groupSizes[i]
            if x not in hash: hash[x] = []
            hash[x].append(i)
            if (len(hash[x]) == x):
                res.append(hash[x])
                hash[x] = []
        return res
1
2
3
4
5
6
7
8
9
10
11
12