账户合并(medium)"/>
[并查集]leetcode721:账户合并(medium)
题目:
题解:
本题是并查集的实际应用题,需要把实际问题转换为我们熟悉的并查集,这点很重要,我本人现在就是很缺乏这种能力,至于怎么提升肯定需要大量做题吧。
思路:
- 1)构建并查集的模板,然后给n个客户进行并查集的初始化。
- 2)构建一个map用来记录<邮箱,邮箱id>。对于邮箱相等的客户,我们进行id的合并;对于邮箱不同的客户,我们就用map记录。
- 3)再构建一个map用来记录<id,邮箱列表>。我们遍历前一个map,将id在同一个联通量中的邮箱,加入邮箱列表。
- 4)最后再遍历第二个map,用来保存结果。
代码如下:
class UnionFind
{
private:vector<int> father; // 父亲vector<int> len; // 树的大小
public:UnionFind(int n) // 构造函数初始化对象{father.resize(n),len.resize(n);for(int i=0;i<n;++i){father[i]=i; // 初始化时父节点指向本身len[i]=1; // 初始化时每个树大小为1}}int find(int x) // 查询树的根{// 在查询所有父节点过程中,顺便进行路径压缩if(father[x]!=x)return father[x]=find(father[x]);else return x;}void merge(int x,int y) // 合并x和y所属的集合{x=find(x),y=find(y);if(x==y)return; // x和y为同一集合不需要合并// 按秩进行合并,小秩向大秩合并if(len[x]<len[y]){father[x]=y;len[y]+=len[x];} else{father[y]=x;len[x]+=len[y];} }
};class Solution {
public:vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {int n=accounts.size();// 1、先初始化[0,n-1]号id的并查集UnionFind uf(n);// 2、用rec1来记录<邮箱,邮箱id>,当出现相同的邮箱时,我们把id进行合并,表示为同一客户unordered_map<string,int> rec1;for(int i=0;i<n;++i){ // 遍历id为i的客户的邮箱for(int j=1;j<accounts[i].size();++j){// 判断是否发现重复邮箱。没有出现则把id和emil记录在map中,出现了重复邮箱,则进行id的合并string emil=accounts[i][j];if(rec1.find(emil)==rec1.end())rec1[emil]=i;else uf.merge(i,rec1[emil]);}}// 3、再用一个rec2来记录<联通量根节点id,邮箱列表>unordered_map<int,vector<string>> rec2;for(auto &[k,v]:rec1)// 将同一集合中的邮箱放在一起,由于已经进行了集合的合并,所以不会出现重复的邮箱{rec2[uf.find(v)].emplace_back(k);}// 4、遍历rec2,来得到最后结果vector<vector<string>> res;for(auto& [k,v]:rec2){vector<string> account;// 将客户的姓名添加进去account.push_back(accounts[k][0]);// 将邮箱进行排序sort(v.begin(),v.end());account.insert(account.end(),v.begin(),v.end());res.push_back(account);}return res;}
};
更多推荐
[并查集]leetcode721:账户合并(medium)
发布评论