题目描述

描述：每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。

在结果列表中，选择 字典序最小 的名字作为真实名字。

示例：

输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)"]

提示：

names.length <= 100000

解题思路

思路1：最直观的想法是，并查集。首先遍历synonyms集合，其中每个synonym中的两个名字n1和n2属于同一个集合，故使用merge函数将n1和n2合并。merge函数实现方法：首先使用search方法分别找到n1、n2的根节点r1、r2，然后将较小的节点挂载在较大节点的父节点上，从而实现根节点为字典序较小的节点。search函数实现方法：如果集合中不包含该节点则将该节点初始化为自己的父节点，反之，如果当前节点父节点不为自己，则递归将父节点的父节点即根节点设为其父节点，并最后返回当前节点父节点即字典序最小节点即根节点。

unordered_map<string,string> ump;
//查找父节点
string search(string &name)
{//集合中不包含该节点则将该节点初始化为其父节点if(ump.count(name)==0)return ump[name]=name;//如果当前节点父节点不为自己 则将父节点的父节点设为其父节点if(ump[name]!=name)ump[name]=search(ump[name]);//返回当前节点父节点即字典序最小节点return ump[name];
}
//将同名格式转换为set格式
//"(Jon,John)","(John,Johnny)" —— Jon,John,Johnny
void merge(string &n1,string &n2)
{//找n1所在集合代表节点string r1=search(n1);//找n2所在集合代表节点string r2=search(n2);//选择代表节点字典序最小的if(r1<r2)ump[r2]=r1;else if(r1>r2)ump[r1]=r2;
}
vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) 
{for(auto synonym:synonyms){int inx1=synonym.find("(");int inx2=synonym.find(",");int inx3=synonym.find(")");auto n1=string(synonym.begin()+inx1+1,synonym.begin()+inx2);auto n2=string(synonym.begin()+inx2+1,synonym.begin()+inx3);//选择字典序较小的作为真实名字merge(n1,n2);}unordered_map<string,int> mp;//将字符串格式转换为键值对格式 //"John(15)" —— John:15for(auto name:names){int pos1=name.find("(");int pos2=name.find(")");auto k=string(name.begin(),name.begin()+pos1);auto v=stoi(string(name.begin()+pos1+1,name.begin()+pos2));//查找每一个名字的根名字mp[search(k)]+=v;}vector<string> res;for(auto n:mp){string s=n.first+'('+to_string(n.second)+')';res.push_back(s);}return res;
}

总结：并查集的本质是一棵树，即同一集合的元素均位于一棵树上，两个元素在同一集合即两个元素所在树的树根相同。本题处理字符串也较为繁琐，但是需要注意，C++中可以使用find函数定位所需查找的分割符位置，然后使用迭代器begin()、end()来获取具体元素。