【C/C++】1282. 用户分组

---

题目链接：1282. 用户分组

题目描述

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

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

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

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

提示:

• groupSizes.length==ngroupSizes.length == ngroupSizes.length==n
• 1⩽n ⩽5001 \leqslant n \leqslant 5001⩽n ⩽500
• 1⩽ groupSizes[i]⩽n1 \leqslant groupSizes[i] \leqslant n1⩽ groupSizes[i]⩽n

示例 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，其中 groupSizes[i] 是第 i 个人所在的组的大小。

现在题目要求我们返回一个组列表，要求按照给定的数组来划分这些人。每个人应该 恰好只 出现在 一个组 中，并且每个人必须在一个组中。

如果有多个答案，返回其中 任何 一个。可以 保证 给定输入 至少有一个 有效的解。

解题思路分析

因为题目保证存在至少一个解，所以我们可以按照每个人所在的组大小和 id 进行排序处理。

排序后可以通过直接遍历来取对应的人数成为一组即可。

具体实现

1. 按照 <组大小, id> 进行存储并排序。
2. 顺序遍历取对应的 id 即可，如果当前组已满就将当前组放入答案数组，然后接着放入新的一个组。

在判断当前组是否满时可以根据当前组第一个人 id 的组大小来判断。

复杂度分析

• 时间复杂度：O(nlog⁡n)O(n \log n)O(nlogn)，其中 n 是数组 groupSize 的长度。需要遍历数组一次得到每个组的大小对应的所有人的编号，然后需要按照组的大小进行排序，然后遍历所有元素完成分组。
• 空间复杂度：O(n)O(n)O(n)，其中 n 是数组 groupSize 的长度。需要记录每个组的大小对应的所有人的编号。

代码实现

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        // 按照 < 组大小，id > 进行存储并排序
        vector<pair<int, int>> vec;
        vec.clear();
        int n = groupSizes.size();
        for(int i = 0; i < n; i++){
            vec.emplace_back(groupSizes[i], i);
        }
        sort(vec.begin(), vec.end());
        // 排序后 组大小 相同的就在一起了
        vector<vector<int>> ans;
        ans.clear();
        vector<int> temp;
        temp.clear();
        // 顺着取即可
        for(int i = 0; i < n; i++){
            temp.emplace_back(vec[i].second);
            if(temp.size() == groupSizes[temp[0]]){
                ans.emplace_back(temp);
                temp.clear();
            }
            
        }
        return ans;
    }
};

总结

• 该题理论上使用 哈希表 的时间复杂度更低，但是由于哈希表也并真正的 O(1)O(1)O(1)，其实是常数级别的 O(1)O(1)O(1)，又因为数据范围较小（n⩽500n \leqslant 500n⩽500），所以这里直接采用排序后直接顺序遍历的用时会更少一点。但是随着数据范围的增加，排序的耗时会凸显出来，这时采用哈希表的做法就更优了。
• 测试结果：

结束语

生活中我们难免会和他人产生摩擦，有时候，退一步海阔天空，换个角度想一想，事情也许并不像我们想象的那么不可调解。对一些无关紧要的小事，不必总记挂在心上。少一些斤斤计较，人生就会快乐更多。新的一天，加油！