LeetCode 721. 账户合并
原题链接
中等
作者:
GRID
,
2021-01-18 10:04:39
,
所有人可见
,
阅读 302
分析
- 具有大小的并查集的考查。
- 第一次把账户的归属利用哈希表mp存起来。
- 第二次使用一个集合哈希表把每一个账户的所有邮件地址存进来,用set是因为要去掉重复的邮件地址。
- 最后把集合哈希表的元素加入到答案数组中。
C++ 代码
class Solution {
public:
int find(int x)
{
if(fa[x]!=x) return fa[x]=find(fa[x]);
return fa[x];
}
void uni(int a,int b)
{
int faa=find(a),fbb=find(b);
if(faa!=fbb)
{
if(siz[faa]>siz[fbb]) //账户a比账户b大,把b加入到a里面
{
fa[fbb]=faa;
siz[faa]+=siz[fbb];
}
else{ //反之把a加入到b里面
fa[faa]=fbb;
siz[fbb]+=siz[faa];
}
}
}
vector<int> fa,siz;
unordered_map<string,int> mp;
vector<vector<string>> ans;
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
int n=accounts.size();
fa = vector<int>(n,0);
siz = vector<int>(n,1);
for(int i=0;i<n;i++) fa[i]=i;
for(int i=0;i<n;i++)
{
for(int j=1;j<accounts[i].size();j++)
{
if(!mp.count(accounts[i][j])) //邮件没有出现,就在哈希表中存一下
{
mp[accounts[i][j]]=i;
}
else{ //邮件之前出现过,合并两个账户
uni(i,mp[accounts[i][j]]);
}
}
}
unordered_map<int,set<string> > user; //账户哈希表,set用于去重
for(int i=0;i<n;i++)
{
fa[i]=find(i);
for(int j=1;j<accounts[i].size();j++)
{
user[fa[i]].insert(accounts[i][j]); //把同一账户的所有邮件地址加入到该账户里
}
}
for(auto x:user) //遍历账户哈希表,加入到答案数组中
{
vector<string> temp;
temp.push_back(accounts[x.first][0]); //先把名字加入到每个容器中
for(auto mail: x.second) //把所有地址加入到临时数组temp中
{
temp.push_back(mail);
}
ans.push_back(temp);
}
return ans;
}
};