在 C++ 中根据人员所属的组大小对人员进行分组
c++server side programmingprogramming更新于 2025/4/15 6:22:17
假设有 n 个人，他们的 ID 在 0 到 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]]
为了解决这个问题，我们将遵循以下步骤 −
- 创建一个映射 m
- 对于 i，范围为 0 到给定数组 a 的大小 – 1
- 将 i 插入到 m[g[i]] 中
- 创建一个名为 res 的矩阵
- 对于映射 m 中的每个元素 i
- 对于 j，范围从 0 到 i 处存在的列表的大小
- 将 i 数组的第 j 个元素插入到 temp 中
- 如果 temp 的大小 = i 的键
- 然后将 temp 作为新行插入到 res 中
- 清除 temp 数组
- 对于 j，范围从 0 到 i 处存在的列表的大小
- return 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, ],]
