Giả sử có n người có ID nằm trong khoảng từ 0 đến n - 1 và mỗi người thuộc đúng một nhóm. Chúng ta có nhóm mảng Kích thước có độ dài n. Mảng này cho biết quy mô nhóm mà mỗi người thuộc về, chúng tôi phải tìm các nhóm ở đó và ID của mọi người mà mỗi nhóm bao gồm.
Giả sử đầu vào là - [3,3,3,3,3,1,3], thì đầu ra là [[5], [0, 1, 2], [3, 4, 6]], Khác có thể giải pháp có thể là [[2,1,6], [5], [0,4,3]] hoặc [[5], [0,6,2], [4,3,1]]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- tạo một bản đồ m
- cho tôi trong phạm vi từ 0 đến kích thước của mảng đã cho a - 1
- chèn i vào m [g [i]]
- tạo một ma trận được gọi là res
- cho mỗi phần tử i trong bản đồ m
- cho j trong phạm vi từ 0 đến kích thước của danh sách có tại i
- chèn phần tử thứ j của mảng i vào tạm thời
- if size of temp =key of i
- sau đó chèn tạm thời vào res dưới dạng hàng mới
- xóa mảng tạm thời
- cho j trong phạm vi từ 0 đến kích thước của danh sách có tại i
- trả lại res.
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
[3,3,3,3,3,1,3]
Đầu ra
[[5, ],[0, 1, 2, ],[3, 4, 6, ],]