C++で所属するグループサイズを指定して人々をグループ化する

IDが0からn-1の範囲にあるn人がいて、各人が正確に1つのグループに属しているとします。長さnの配列groupSizesがあります。この配列は、各人が属するグループサイズ、存在するグループ、および各グループに含まれる人のIDを見つける必要があることを示しています。

入力が− [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]]

これを解決するには、次の手順に従います-

• 1つのマップを作成するm
• 0から指定された配列a–1のサイズまでの範囲のiの場合
  • iをm[g[i]]
  に挿入します
• resと呼ばれる1つのマトリックスを作成します
• マップmの各要素iについて
  • 範囲0からiに存在するリストのサイズまでのjの場合
    • iの配列のj番目の要素をtempに挿入します
    • tempのサイズ=iのキー
      • 次に、tempを新しい行としてresに挿入します
      • 一時配列をクリアする
• 解像度を返します。

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<vector<int>> groupThePeople(vector<int>& g) {
      map <int, vector <int> > m;
      for(int i = 0; i < g.size(); i++){
         m[g[i]].push_back(i);
      }
      vector < vector <int> > res;
      map <int, vector <int> > :: iterator i = m.begin();
      vector <int> temp;
      while(i != m.end()){
         for(int j = 0; j < i->second.size(); j++){
            temp.push_back(i->second[j]);
            if(temp.size() == i->first){
               res.push_back(temp);
               temp.clear();
            }
         }
         i++;
      }
      return res;
   }
};
main(){
   vector<int> v = {3,3,3,3,3,1,3};
   Solution ob;
   print_vector(ob.groupThePeople(v));
}

入力

[3,3,3,3,3,1,3]

出力

[[5, ],[0, 1, 2, ],[3, 4, 6, ],]