Leetcode:1282. 用户分组(贪心,hash)

    科技2022-07-10  230

    1282. 用户分组

    有 n 位用户参加活动,他们的 ID 从 0 到 n - 1,每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 groupSizes,其中包含每位用户所处的用户组的大小,请你返回用户分组情况(存在的用户组以及每个组中用户的 ID)。

    你可以任何顺序返回解决方案,ID 的顺序也不受限制。此外,题目给出的数据保证至少存在一种解决方案。

    示例 1:

    输入:groupSizes = [3,3,3,3,3,1,3] 输出:[[5],[0,1,2],[3,4,6]] 解释: 其他可能的解决方案有 [[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

    这道题还是贪心的思想个人在于,我们首先将用户组相同的用户存在一区,然后每次拿出来一个用户组大小,显而易见这是必然能全部拿走的,所以每次贪心的拿走我们需要的就OK了,因此这里需要两次分解


    第一次先把用户大概的分到相同用户组里,第二次再在用户组里分出相等的分量,问题就解决了

    class Solution { public: vector<vector<int>> groupThePeople(vector<int>& groupSizes) { unordered_map<int,vector<int>>groups; for(int i=0;i<groupSizes.size();i++){ groups[groupSizes[i]].push_back(i); } vector<vector<int>>ans; for(auto group=groups.begin();group!=groups.end();group++){ const int& gsize=group->first; vector<int>&users=group->second; for(auto iter=users.begin();iter!=users.end();iter=next(iter,gsize)){ vector<int>dummy(iter,next(iter,gsize)); ans.push_back(dummy); } } return ans; } };
    Processed: 0.023, SQL: 8