跳到主要内容

1282. 用户分组

mid 哈希

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

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

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

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

image-20220812150156935

哈希​

房间大小 : 房间数组

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
}

空间上花的有点多，因为最后还要整合成一个新数组返回

更好的哈希​

image-20220812150335464

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
}