1282. 用户分组

原题链接：1282. 用户分组

solution:

        排序

class Solution {
public:
    typedef pair<int, int> PII;
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<PII> group;//first保存所在组大小,second保存第i个人
        int n = groupSizes.size();
        for(int i = 0;i < n;i++) {
            group.push_back(make_pair(groupSizes[i], i));
        }

        sort(group.begin(), group.end());

        vector<vector<int>> res;
        vector<int> path;
        for(int i = 0,j = group[0].first;i < n;i++) {
            if(path.size() == j) {
                res.push_back(path);
                path.clear();
                j = group[i].first; //更新组大小
            }
            path.push_back(group[i].second);    //存储组
        }
        res.push_back(path);
        return res;
    }
};

hash

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        unordered_map<int, vector<int>> hash;
        vector<vector<int>> res;
        for(int i = 0;i < groupSizes.size();i++) {
            int x = groupSizes[i];
            hash[x].push_back(i);
            if(hash[x].size() == x) {
                res.push_back(hash[x]);
                hash[x].clear();
            }
        }
        return res;
    }
};