题目分析
这个题目一看就是一个搜索类的题目,其实搜索类的题目我已经拿出来很多了。这个题目又要拿出来说一说,因为它不同于一般的图,一般的图告诉我们邻接矩阵,而这个图类似于朋友圈题目,只告诉我们两两关系,这个题目最直观的方法是并查集,但是如何使用DFS和BFS去求解呢?希望小伙伴们先尝试一下。
DFS
和普通的矩阵图问题不同的是,在地图搜索问题中,往往给定一个起始点,向四个方向搜索即可。但是这个问题没有邻接矩阵,我们要构造一个临界矩阵,找到某个名字和其他名字的关系。
在DFS中,我们建立一个HashMap,其中键为某个名字,值是一个哈希表,其中存放着所有和它相同的名字的集合。
然后建立一个visited集合,存放所有访问过的名字的集合。从第一个名字开始搜索,所有搜索过的名字都加入visited集合,搜完与第一个名字相同的所有名字,并且在搜索过程中取出最小的名字作为真实名字。然后再搜索第二个名字,如果第二个名字和第一个名字是同一个名字,则第二个名字在搜索第一个名字的时候已经加入了visited,继续搜索第三个名字。
算法的**时间复杂度为$O(n + m)$,因为最坏情况下,每个人都和其他所有人名字相同,因此每个键对应的值都是其他所有人的名字,所以空间复杂度为$O(n^2)$**,其中n为名字数量,m为相同名字的关系对数量。
1 | #include<iostream> |
BFS
BFS和DFS的预处理过程完全相同,只是我们在搜索时,搜到某个名字,如果某个名字不在visited中,则将其加入visited,说明该名字已经访问过,然后同时将和它相同的所有名字都同时加入到队列中。
这里也不过多赘述,思路也比较简单,多写一些DFS和BFS就会发现它们都是相同的模板。
算法的**时间复杂度为$O(n + m)$,空间复杂度为$O(n^2)$**,其中n为名字数量,m为相同名字的关系对数量。
1 | #include<iostream> |
并查集
并查集也是解决这个问题的好方法,虽然并查集没有DFS和BFS那样使用范围大,但是解决朋友圈数量,岛屿个数等等这类问题,最好的方法就是使用并查集。我在数据结构和算法中的算法部分也专门提到过这个方法。
这里再大致说一下,要新建一个并查集UF类,要在类中实现两个最最重要的方法,一个是find,一个是union,在C++语言中不能写union方法,就用merge代替。其中find是找到带头人,merge是合并带头人。什么意思呢?这个问题就是一个合并问题,相同名字合并在一起进行计数。一开始我们让每一个名字的带头人都是自己,数量就是自己的数量。
然后访问合并关系,当两个名字相同时,就让其中一个带头人的带头人是另一个带头人。比如A和B是相同的名字,原本A的带头人是ARoot,ARoot的带头人就是它自己。B的带头人是BRoot,BRoot的带头人也是它自己。我们要合并A和B,就说让ARoot的带头人是BRoot,或者让BRoot的带头人是ARoot,这样我们查找A的带头人和B的带头人都是同一个人。这就相当于合并了A和B。非常类似于生活中的例子,本来有一个校长A,也有一个校长B,那么合并两个学校后,让一个校长变成副校长,听从另一个校长的管理。
在合并时,如果两个带头人不相同,则取较小的那个名字为真正的带头人,并且让较小名字的带头人的数量加上较大名字带头人的数量即可。
最后合并完以后,查看所有的带头人,有多少带头人就有多少个不同的名字,再查看每个名字对应的数字,将其转换为字符串并return即可。
在merge时,对于每一对相同的名字,都要进行find,最坏情况下,每一次find都要向上搜索m次。因此算法的**时间复杂度为$O(n + m^2)$,空间复杂度为$O(n + m)$**,其中n为名字数量,m为相同名字的关系对数量。
因为find的过程非常简单,几乎不用花费很长时间,因此时间消耗和DFS或者BFS几乎差不多。
1 | #include<iostream> |
刷题总结
上面三个方法都需要小伙伴们掌握,能用并查集解决的问题,使用DFS和BFS基本上都可以解决,但是并查集的思想非常好,希望小伙伴能够认真学习。