注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(70)-朋友圈[算法]  

2018-01-30 07:19:55|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
问题:假设一个班上有N个同学。同学之间有些是朋友,有些不是。朋友关系是可以传递的。比如A是B的直接朋友,B是C的直接朋友,那么A是C的间接朋友。我们定义朋友圈就是一组直接或间接朋友的同学。输入一个N*N的矩阵M表示班上的朋友关系,如果M[i][j]=1,那么同学i和同学j是直接朋友。请问该班有多少个朋友圈?

例如输入如下的数组,则表明同学0和同学1是朋友,他们组成一个朋友圈。而同学2一个人组成一个朋友圈。因此输出2。

[[1,1,0],

 [1,1,0],

 [0,0,1]]


分析:这是LeetCode的第547题。


首先我们注意到朋友关系是对称的,也就是A和B是朋友,那么B和A自然也是朋友。那么输入的矩阵M应该是沿着对角线对称的。另外,一个人和他自己是朋友,也就是矩阵M中对角线上的所有数字都是对称的。


接着我们把用矩阵表示的朋友关系转化成图。每个同学就是图中的一个节点,而直接朋友就是图中的边。如果同学i和同学j是直接朋友,我们就在节点i和节点j之间添加一条边。示例中的矩阵转化成图之后如下图所示。不难发现这个图由两个子图组成,每个子图都是一个朋友圈,因此这个班有两个朋友圈。


程序员面试题精选100题(70)-朋友圈[算法] - 何海涛 - 微软、Google等面试题

 

一个表示N个同学朋友关系的图有N个节点。由于我们知道每个人都是自己的朋友,因此我们在初始化时,这个图有N个子图,每个子图都只包含一个节点。接下来我们扫描矩阵M。当M[i][j]=1时,同学i和同学j是直接朋友,因此他们一定在一个朋友圈里。


这个时候我们要解决两件问题:


(1)如何判断同学i和同学j是不是已经在同一个朋友圈即子图里,也就是判断节点i和节点j是不是联通;


(2)如果同学i和同学j之前不联通(不在同一个子图里),我们如何连接他们所在子图,也就是合并两个子图。


通常我们可以用DFS判断节点i和节点j是否联通。如果一个图有n条边,因此DFS需要O(n)的时间。我们对矩阵M中的每条边的两个节点都要做这样的判断,因此总的时间复杂度是O(n^2)。注意n是图中边的数量。


幸运的是我们可以利用一种叫并查集的数据结构进行优化。顾名思义,这种数据结构主要能高效完成两件事情:(1)合并两个子图;(2)判断两个节点是否联通。并查集用途正好完美匹配前面我们提到的要解决的两件问题。接下来我们详细讨论怎么使用并查集。


在使用并查集是,每个子图都类似于树状结构。子图中的节点都有父节点,根节点的父节点就是他自身。因此同一个子图的根节点一定是同一个。我们判断两个节点是不是联通也就是它们是不是在同一个子图,只需要看它们的根节点是不是相同就知道了。


我们定义长度为N的数组fathers存储N个节点的父节点。初始化图的时候,每个节点组成一个子图,因此每个节点都是各自子图里的根节点,及所有的fathers[i]=i。


有了这个fathers数组,我们想知道节点i所在的子图的根节点,我们得沿着指向父节点的边遍历,看起来仍然是O(n)的时间复杂度。但我们在这里做一个优化。


由于我们真正关心的是节点i的根节点是谁而不是它的父节点。因此我们可以在fathers[i]存储它的根节点。当我们第一次找节点i的根节点时,我们还需要沿着指向父节点的边遍历直到找到根节点。一旦我们找到了个它的根节点,我们把根节点存到fathers[i]里面。以后再求第i个节点的根节点时我们马上就知道了。上述的优化叫做路劲压缩。


接下来考虑怎么合并两个子图。假设第一个子图的根节点是i,第二个子图的根节点是j。如果我们把fathers[i]设为j,相等于把整个第一个子图挂在了节点j的下面,让第一个子图成为第二个子图的一部分,也就是合并了两个子图。


下面就是基于并查集的Java代码:


程序员面试题精选100题(70)-朋友圈[算法] - 何海涛 - 微软、Google等面试题

 

在上述代码的函数findFather实施了路径压缩。有了并查集的优化,整个算法的时间复杂度是O(n),使用了路径压缩的并查集的常数非常小可以忽略(其中n是图中边的条数)。


本文转载自微信公众号青云算法扫描下面的二维码,关注“青云算法”微信公众号,学习更多高频算法面试题的解法。

程序员面试题精选100题(65)-每天的温度[算法] - 何海涛 - 微软、Google等面试题

  评论这张
 
阅读(776)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018