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

解题思路

这道题的核心思路是贪心算法结合哈希表分组。

首先理解题目要求：每个人都有一个期望的组大小，我们需要将具有相同期望组大小的人尽可能地分在一起，当一个组达到期望大小时就立即输出。

解题思路：

  1. 按组大小分类：使用哈希表将所有人按照他们期望的组大小进行分类。比如所有期望组大小为3的人放在一起。

  2. 贪心分组：对于每种组大小，维护一个临时组。当我们遇到一个需要该组大小的人时，就将其加入临时组。一旦临时组达到了期望的大小，立即将这个组添加到结果中，并清空临时组开始新的分组。

  3. 实现细节：可以用哈希表存储每个组大小对应的当前临时组，也可以在遍历过程中动态维护。

这种贪心策略是正确的，因为题目保证了输入一定有解，而且我们只需要返回任意一种有效分组方案。通过这种方法，我们能够以线性时间复杂度解决问题。

代码实现

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        unordered_map<int, vector<int>> groups;
        vector<vector<int>> result;
        
        for (int i = 0; i < groupSizes.size(); i++) {
            int size = groupSizes[i];
            groups[size].push_back(i);
            
            // 当当前组大小达到期望大小时，添加到结果并清空
            if (groups[size].size() == size) {
                result.push_back(groups[size]);
                groups[size].clear();
            }
        }
        
        return result;
    }
};

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        groups = {}
        result = []
        
        for i, size in enumerate(groupSizes):
            if size not in groups:
                groups[size] = []
            
            groups[size].append(i)
            
            # 当当前组大小达到期望大小时，添加到结果并清空
            if len(groups[size]) == size:
                result.append(groups[size])
                groups[size] = []
        
        return result

public class Solution {
    public IList<IList<int>> GroupThePeople(int[] groupSizes) {
        Dictionary<int, List<int>> groups = new Dictionary<int, List<int>>();
        IList<IList<int>> result = new List<IList<int>>();
        
        for (int i = 0; i < groupSizes.Length; i++) {
            int size = groupSizes[i];
            
            if (!groups.ContainsKey(size)) {
                groups[size] = new List<int>();
            }
            
            groups[size].Add(i);
            
            // 当当前组大小达到期望大小时，添加到结果并清空
            if (groups[size].Count == size) {
                result.Add(new List<int>(groups[size]));
                groups[size].Clear();
            }
        }
        
        return result;
    }
}

var groupThePeople = function(groupSizes) {
    const sizeMap = new Map();
    const result = [];
    
    for (let i = 0; i < groupSizes.length; i++) {
        const size = groupSizes[i];
        
        if (!sizeMap.has(size)) {
            sizeMap.set(size, []);
        }
        
        sizeMap.get(size).push(i);
        
        if (sizeMap.get(size).length === size) {
            result.push(sizeMap.get(size));
            sizeMap.set(size, []);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有n个人一次，每次操作都是常数时间
空间复杂度O(n)哈希表最多存储所有人的索引，结果数组也需要O(n)空间

相关题目