发表于 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

• LC 题目链接