Group the People Given the Group Size They Belong To จัดกลุ่มตามขนาดกลุ่มใน C++

มี n คน ID 0 ถึง n-1 แต่ละคนอยู่ในกลุ่มขนาด groupSizes[i] จัดกลุ่มให้ถูกต้อง (แต่ละกลุ่มมีขนาดตรงกับที่กำหนด)

ตัวอย่าง: [3,3,3,3,3,1,3] → [[5],[0,1,2],[3,4,6]]

วิธีแก้ปัญหา (Hash Map Grouping)

1. map m: key = group size, value = ลิสต์คนที่อยากอยู่กลุ่มขนาดนั้น
2. วนทุกคน i: ใส่ i ลง m[groupSizes[i]]
3. สร้างผลลัพธ์ res:
   • วนแต่ละ group size ใน m:
     • แบ่งลิสต์คนเป็นชุดๆ ละ group size ใส่ลง res

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> 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;
        vector<int> temp;
        for (auto& p : m) {
            for (int id : p.second) {
                temp.push_back(id);
                if (temp.size() == p.first) {
                    res.push_back(temp);
                    temp.clear();
                }
            }
        }
        return res;
    }
};

int main() {
    vector<int> v = {3,3,3,3,3,1,3};
    Solution ob;
    print_vector(ob.groupThePeople(v));
    return 0;
}

Input

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

Output

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