1282. 用户分组
mid 哈希
有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的唯一 ID 。
给定一个整数数组 groupSizes ，其中 groupSizes[i] 是第 i 个人所在的组的大小。例如，如果 groupSizes[1] = 3 ，则第 1 个人必须位于大小为 3 的组中。
返回一个组列表，使每个人 i 都在一个大小为 groupSizes[i] 的组中。
每个人应该 恰好只 出现在 一个组 中，并且每个人必须在一个组中。如果有多个答案，返回其中 任何 一个。可以 保证 给定输入 至少有一个 有效的解。
哈希
房间大小 : 房间数组
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
| type room []int
type rooms []room
func groupThePeople(groupSizes []int) (res [][]int) {
hash := map[int]rooms{} // 房间大小:房间数组
for i, size := range groupSizes {
if _, ok := hash[size]; !ok {
hash[size] = rooms{room{i}}
} else {
rooms := hash[size]
roomsAllFull := true
for j := 0; j < len(rooms); j++ {
if len(rooms[j]) < size {
// 没满 把i放进去
rooms[j] = append(rooms[j], i)
roomsAllFull = false
break
}
}
if roomsAllFull {
// 房间都满了 再加一个
hash[size] = append(hash[size], room{i})
}
}
}
for _, rooms := range hash {
for _, room := range rooms {
res = append(res, room)
}
}
return res
}
|
空间上花的有点多，因为最后还要整合成一个新数组返回
更好的哈希
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
}
|
