1282-用户分组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

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

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

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

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

示例 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]]

提示：

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

方法一：哈希表

由于给定的输入一定存在有效的解，因此对于数组 groupSizes 中的每个元素 x，当 x 在数组中出现 y 次时，y 一定能被 x 整除，且大小为 x 的组有 \dfrac{y}{x 个。

首先将每个人的编号按照组的大小划分，使用哈希表记录每个组的大小对应的所有人的编号。然后遍历哈希表，对于大小为 x 的组，得到对应的所有人编号列表，将列表的大小记为 y，则 y 一定能被 x 整除，将列表分成 \dfrac{y}{x 个大小为 x 的组，并将每个组添加到答案中。遍历结束之后，即完成分组。

考虑示例 1 的分组。

  1. 根据数组 groupSizes 得到每个组的大小对应的所有人的编号：大小为 1 的组对应的编号列表是 [5]，大小为 3 的组对应的编号列表是 [0, 1, 2, 3, 4, 6]。

  2. 将每个组的大小对应的编号列表分成特定大小的列表。

    • 大小为 1 的组对应的编号列表的长度是 1，因此有 1 个大小为 1 的组：[5]。

    • 大小为 3 的组对应的编号列表的长度是 6，因此有 2 个大小为 3 的组：[0, 1, 2], [3, 4, 6]。

  3. 最终分组情况是 [[5], [0, 1, 2], [3, 4, 6]。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        groups = defaultdict(list)
        for i, size in enumerate(groupSizes):
            groups[size].append(i)
        ans = []
        for size, people in groups.items():
            ans.extend(people[i: i + size] for i in range(0, len(people), size))
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        Map<Integer, List<Integer>> groups = new HashMap<Integer, List<Integer>>();
        int n = groupSizes.length;
        for (int i = 0; i < n; i++) {
            int size = groupSizes[i];
            groups.putIfAbsent(size, new ArrayList<Integer>());
            groups.get(size).add(i);
        }
        List<List<Integer>> groupList = new ArrayList<List<Integer>>();
        for (Map.Entry<Integer, List<Integer>> entry : groups.entrySet()) {
            int size = entry.getKey();
            List<Integer> people = entry.getValue();
            int groupCount = people.size() / size;
            for (int i = 0; i < groupCount; i++) {
                List<Integer> group = new ArrayList<Integer>();
                int start = i * size;
                for (int j = 0; j < size; j++) {
                    group.add(people.get(start + j));
                }
                groupList.add(group);
            }
        }
        return groupList;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public IList<IList<int>> GroupThePeople(int[] groupSizes) {
        Dictionary<int, IList<int>> groups = new Dictionary<int, IList<int>>();
        int n = groupSizes.Length;
        for (int i = 0; i < n; i++) {
            int size = groupSizes[i];
            groups.TryAdd(size, new List<int>());
            groups[size].Add(i);
        }
        IList<IList<int>> groupList = new List<IList<int>>();
        foreach (KeyValuePair<int, IList<int>> pair in groups) {
            int size = pair.Key;
            IList<int> people = pair.Value;
            int groupCount = people.Count / size;
            for (int i = 0; i < groupCount; i++) {
                IList<int> group = new List<int>();
                int start = i * size;
                for (int j = 0; j < size; j++) {
                    group.Add(people[start + j]);
                }
                groupList.Add(group);
            }
        }
        return groupList;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        unordered_map<int, vector<int>> groups;
        int n = groupSizes.size();
        for (int i = 0; i < n; i++) {
            int size = groupSizes[i];
            groups[size].emplace_back(i);
        }
        vector<vector<int>> groupList;
        for (auto &[size, people] : groups) {
            int groupCount = people.size() / size;
            for (int i = 0; i < groupCount; i++) {
                vector<int> group;
                int start = i * size;
                for (int j = 0; j < size; j++) {
                    group.emplace_back(people[start + j]);
                }
                groupList.emplace_back(group);
            }
        }
        return groupList;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
typedef struct Array {
    int *arr;
    int pos;
    int size;
} Array;

Array* creatArray(int size) {
    Array *obj = (Array *)malloc(sizeof(Array));
    obj->arr = (int *)malloc(sizeof(int) * size);
    obj->size = size;
    obj->pos = 0;
    return obj;
}

void freeArray(Array *obj) {
    free(obj->arr);
    free(obj);
}

int** groupThePeople(int* groupSizes, int groupSizesSize, int* returnSize, int** returnColumnSizes){
    Array **groups = (Array **)malloc(sizeof(Array *) * (groupSizesSize + 1));
    for (int i = 0; i <= groupSizesSize; i++) {
        groups[i] = creatArray(groupSizesSize);
    }
    for (int i = 0; i < groupSizesSize; i++) {
        int size = groupSizes[i];
        groups[size]->arr[groups[size]->pos++] = i;
    }
    int **groupList = (int **)malloc(sizeof(int *) * groupSizesSize);
    *returnColumnSizes = (int *)malloc(sizeof(int) * groupSizesSize);
    int pos = 0;
    for (int k = 0; k <= groupSizesSize; k++) {
        if (groups[k]->pos == 0) {
            continue;
        }
        int size = k;
        int groupCount = groups[k]->pos / size;
        for (int i = 0; i < groupCount; i++) {
            int *group = (int *)malloc(sizeof(int) * size);
            int start = i * size, index = 0;
            for (int j = 0; j < size; j++) {
                group[index++] = groups[k]->arr[start + j];
            }
            (*returnColumnSizes)[pos] = size;
            groupList[pos++] = group;
        }
    }
    *returnSize = pos;
    for (int i = 0; i <= groupSizesSize; i++) {
        freeArray(groups[i]);
    }
    return groupList;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var groupThePeople = function(groupSizes) {
    const groups = new Map();
    const n = groupSizes.length;
    for (let i = 0; i < n; i++) {
        const size = groupSizes[i];
        if (!groups.has(size)) {
            groups.set(size, []);
        }
        groups.get(size).push(i);
    }
    const groupList = [];
    for (const [size, people] of groups.entries()) {
        const groupCount = Math.floor(people.length / size);
        for (let i = 0; i < groupCount; i++) {
            const group = [];
            const start = i * size;
            for (let j = 0; j < size; j++) {
                group.push(people[start + j]);
            }
            groupList.push(group);
        }
    }
    return groupList;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
func groupThePeople(groupSizes []int) (ans [][]int) {
    groups := map[int][]int{}
    for i, size := range groupSizes {
        groups[size] = append(groups[size], i)
    }
    for size, people := range groups {
        for i := 0; i < len(people); i += size {
            ans = append(ans, people[i:i+size])
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 groupSize 的长度。需要遍历数组一次得到每个组的大小对应的所有人的编号，然后需要遍历所有元素完成分组。

  • 空间复杂度：O(n)，其中 n 是数组 groupSize 的长度。空间复杂度主要取决于哈希表，哈希表需要 O(n) 的空间记录每个组的大小对应的所有人的编号。

 Comments
On this page
1282-用户分组