【leetcode】【2022/8/12】1282. 用户分组

问题描述：

• 有 n 个人（分别被标记为 0 到 n-1），他们被分到未知数量的组中。
  • 给定数组 groupSizes，其中 groupSizes[i] 是第 i 个人所在的组的大小。
  • 返回组列表。【即一个数组保存组中成员的索引，多个数组组成多个组】
• 例子：
  • 输入：groupSizes = [3,3,3,3,3,1,3]。
  • 输出：[[5],[0,1,2],[3,4,6]]。

核心思路：

• 纯模拟题，学会用数据结构进行映射即可。
  • 将所有处在同一大小数组的索引存放在一起，如处在组大小为 1 的索引存放在同一堆中，后续再在这一堆中不断取索引并生成大小为 1 的组。

代码实现：

• 代码实现如下：

  class Solution
  {
  public:
      vector<vector<int>> groupThePeople(vector<int>& groupSizes)
      {
          int m = groupSizes.size();
          unordered_map<int, vector<int>> mapped;
          for(int i = 0; i < m; ++i)
              mapped[groupSizes[i]].push_back(i);
          vector<vector<int>> ans;
          for(auto& [cnt, vec] : mapped)
          {
              int i = 0;
              while(i < vec.size())
              {
                  vector<int> tmp;
                  for(int j = 0; j < cnt; ++j)
                      tmp.push_back(vec[i++]);
                  ans.push_back(tmp);
              }
          }
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24

• 评论中 mike-meng 网友的代码实现：【用迭代器参数构造数组，更优雅】

  class Solution {
  public:
      vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
          unordered_map<int,vector<int>> group;
          vector<vector<int>> res;
          
          for(int i = 0;i < groupSizes.size(); ++i){
              group[groupSizes[i]].push_back(i);
          }
          for(auto & it : group){
              for(auto curr = it.second.begin(); curr != it.second.end(); curr += it.first){
                  res.push_back(vector<int>(curr,curr+it.first));
              }
          }
          return res;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17