JZX轻语：简
LeetCode 1282 - 用户分组
发表于2024年07月16日
有两种方法：一种是基于排序，即先对groupSizes带上序号按(组大小, 序号)进行排序，然后遍历上述有序的数组，将相同大小(相同组大小的元素连续分布)的分组放入同一个组；另一种则使用哈希表，记录映射组大小 -> 当前组的序号列表，当某个组大小对应的序号列表长度达到threshold时，将其放入结果列表中，并重置(清空)列表。
基于排序的做法：
class Solution:
def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
# 带上序号, 按(组大小, 序号)排序
idx_list_with_group_size = sorted(enumerate(groupSizes), key=lambda item: (item[1], item[0]))
ans = []
# 当前组
cur_group = []
for idx, group_size in idx_list_with_group_size:
cur_group.append(idx)
if len(cur_group) == group_size: # 当前组满员(达到group_size)
ans.append(list(cur_group))
# 新建一组继续来
cur_group = []
return ans基于哈希表的做法
from collections import defaultdict
class Solution:
def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
ans = []
cur_group_map = defaultdict(list) # 组大小 -> 当前组的序号列表
for idx, group_size in enumerate(groupSizes):
# 根据组大小找到当前组, 并将当前序号放入
cur_group = cur_group_map[group_size]
cur_group.append(idx)
if len(cur_group) == group_size:
# 当前组满员(达到group_size), 放入结果列表
ans.append(list(cur_group))
# 重置当前组
cur_group.clear()
return ans