จัดกลุ่มคนตามขนาดกลุ่มที่พวกเขาอยู่ใน C++

สมมติว่ามี n คนที่มี ID อยู่ในช่วง 0 ถึง n - 1 และแต่ละคนอยู่ในกลุ่มเดียวกัน เรามีอาร์เรย์ groupSizes ของความยาว n อาร์เรย์นี้บ่งชี้ว่าขนาดกลุ่มที่แต่ละคนเป็นสมาชิก เราต้องหากลุ่มที่มีอยู่และ 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]]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างหนึ่งแผนที่ m
• สำหรับฉันในช่วง 0 ถึงขนาดของอาร์เรย์ที่กำหนด a – 1
  • ใส่ i เข้าไปใน m[g[i]]
• สร้างเมทริกซ์หนึ่งชื่อ res
• สำหรับแต่ละองค์ประกอบ i ในแผนที่ m
  • สำหรับ j ในช่วง 0 ถึงขนาดของรายการที่แสดงที่ i
    • แทรกองค์ประกอบ jth ของอาร์เรย์ของ i ลงใน 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, ],]