题目描述

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

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

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

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

样例

输入：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]]。

输入：groupSizes = [2,1,3,3,3,2]
输出：[[1],[0,5],[2,3,4]]

限制

• groupSizes.length == n
• 1 <= n <= 500
• 1 <= groupSizes[i] <= n

算法

(哈希表) $O(n)$

1. 建一个哈希表，key 为 组的人数，value 为一个 数对（表示以当前人数的 key 下，最后一次创建出的组的人数和该组的下标）。
2. 例如，样例 1 中的 3，一开始哈希表中为空，则在哈希表中插入键为 3，值为 [0 (人数), 0 (组的下标)]。如果这个组的人数等于了规定的人数，则人数清零，创建一个新的组。
3. 根据这个哈希表，就可以在对应组中插入当前这个人的 ID。
4. 由于题目保证了至少有一个有效解，所以按照这个方法一定可以找到一个解。

时间复杂度

• 每个人的操作时间复杂度都是常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的空间存放哈希表以及答案，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        int n = groupSizes.size();
        vector<vector<int>> g;
        unordered_map<int, pair<int, int>> sz;

        for (int i = 0; i < n; i++) {
            int x = groupSizes[i];

            if (sz.find(x) == sz.end() || sz[x].first == x) {
                sz[x].first = 0;
                sz[x].second = g.size();
                g.push_back({});
            }

            g[sz[x].second].push_back(i);
            sz[x].first++;
        }

        return g;
    }
};