用户分组

难度: Medium

有 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

Submission

运行时间: 25 ms

内存: 16.2 MB

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        dic=defaultdict(list)
        ans=[]
        for i,size in enumerate(groupSizes):            
            dic[size].append(i)
        for k,v in dic.items():
            for j in range(len(v)//k):
                ans.append(v[j*k : (j+1)*k])
        return ans

Explain

这道题的解法是使用哈希表记录每个人的索引，根据他们应属于的组大小。首先，创建一个字典（使用defaultdict，避免键不存在的情况），用于存储每个组大小及其对应的成员列表。然后，遍历给定的groupSizes数组，将每个人的索引加入到对应组大小的列表中。完成这一步后，将每个组大小的列表中的成员按照组大小分组。如果一个组大小为k，那么就将这个列表中的前k个成员分为一组，接着是下一个k个成员，依此类推。最终，将所有这些小组收集到一个结果列表中返回。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        dic = defaultdict(list)  # 创建字典，用于存储组大小和对应的成员索引
        ans = []  # 最终返回的分组列表
        for i, size in enumerate(groupSizes):  # 遍历每个人和他们的组大小
            dic[size].append(i)  # 将人的索引加入对应组大小的列表
        for k, v in dic.items():  # 遍历字典，k是组大小，v是成员索引列表
            for j in range(len(v) // k):  # 将列表分为大小为k的子列表
                ans.append(v[j*k : (j+1)*k])  # 添加到结果列表
        return ans  # 返回结果

Explore

在给定算法中，通过遍历`groupSizes`数组，并将每个人的索引加入到对应组大小的列表中，可以保证每个列表最终包含的元素数量是组大小的整数倍。这是因为数组的索引和组大小是一一对应的。在进行分组时，使用`for j in range(len(v) // k)`循环确保每次从列表中取出的元素正好是k个，这样就可以确保每个组的成员数量恰好等于其组大小。如果列表长度不是组大小的整数倍，由于每个人都有一个明确的组大小，所以不会出现这种情况。

如果`groupSizes`数组中的所有值都相同，那么哈希表将只包含一个键，其对应的值是一个非常大的列表，包括所有的索引。这种情况下，哈希表的空间利用率较低，因为只使用了一个键值对，但是处理速度不会受到显著影响。遍历和分组的时间复杂度仍然保持为O(n)，其中n是数组的长度。

在这个算法中，选择使用`defaultdict`是为了避免在字典中手动检查和初始化键的存在。使用`defaultdict`可以自动为新的组大小初始化一个空列表，这样在添加索引时可以直接进行。如果使用普通字典，每次添加新索引前，首先需要检查键是否存在于字典中，如果不存在，则需要先创建一个空列表。这会增加代码的复杂性和出错的概率。

在本题的解法中，组内成员的ID是根据它们在原始`groupSizes`数组中的顺序来添加到各个组中的。因此，组内成员的ID顺序是按照它们在输入数组中出现的顺序。通常，这种顺序是足够的，除非题目有额外的要求需要按特定顺序排序组内成员。如果需要特定的排序顺序，可以在添加到结果列表之前对每个小组进行排序。