acwing2022秋招每日一题 1282. 用户分组()

题目

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

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

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

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

思路

对于每个人,用hash存放每个人组别大小和下标。当hash的大小与组别大小一样时,加到结果集后面,最后输出。

解法

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> res;
        // 建立一个哈希结构用来放尺寸和对应的下标
        unordered_map<int, vector<int>> hash;
        for (int i = 0; i < groupSizes.size(); i++)
        {
            /* code */
            int size = groupSizes[i];
            hash[size].push_back(i);
            if (hash[size].size() == size)
            {
                res.push_back(hash[size]);
                hash[size].clear();
            }
        }
        return res;
    }
};
————————

题目

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

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

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

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

思路

对于每个人,用hash存放每个人组别大小和下标。当hash的大小与组别大小一样时,加到结果集后面,最后输出。

解法

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> res;
        // 建立一个哈希结构用来放尺寸和对应的下标
        unordered_map<int, vector<int>> hash;
        for (int i = 0; i < groupSizes.size(); i++)
        {
            /* code */
            int size = groupSizes[i];
            hash[size].push_back(i);
            if (hash[size].size() == size)
            {
                res.push_back(hash[size]);
                hash[size].clear();
            }
        }
        return res;
    }
};