本文主要是介绍【LeetCode】LeetCode 547. 省份数量(Java版 什么是并查集),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
📝个人主页:哈__
期待您的关注
一、题目描述
有 n
个城市,其中一些彼此相连,另一些没有相连。如果城市 a
与城市 b
直接相连,且城市 b
与城市 c
直接相连,那么城市 a
与城市 c
间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个 n x n
的矩阵 isConnected
,其中 isConnected[i][j] = 1
表示第 i
个城市和第 j
个城市直接相连,而 isConnected[i][j] = 0
表示二者不直接相连。
返回矩阵中 省份 的数量。
二、思路讲解
这是一道有关图的算法题目,题目当中给出了这样的描述:共有n个城市,其中的一些彼此相连,一些没有连接,如果a与b相连并且b与c相连,那么a与c也相连,这不就是连通性嘛。在看看这道题让求的是什么,求的是省份的数量,而一个省份内的地点之间都是连通的,题目让我们返回省份的值。我们的目标就是把每一个地区分到一个省份当中。
在这里我要给大家先讲解一种概念“并查集”。
什么是并查集?在我看来就是将图中的结点进行分类的操作,“并”就是将两个结点分类到一起,“查”就是查找结点到底是属于哪个类的。
这样子的描述不够清晰,我引入这样的一个例子。
我在以前看电视剧的时候,总是会有双方交战的场景,我当时就在想,他们的双方是如何分清谁是谁的,难道不会打错人吗?青青草原的绿草已经被羊羊们吃光了,羊羊们为了争夺资源开始了内战,在某一天喜羊羊带领着“喜门”大军去占领一片新的草原,沸羊羊带领着“沸门”大军也去争夺这片草原。两军在小路交叉口遇见。
这次对决的双方羊数很多,假定羊都是白色的,无法区分,我们强制在两只羊交战之前都要自报家门,如果这两只羊是一个阵营的那么就不交战,那么该如何自报家门呢?乐羊羊问道:“你是哪一个阵营的,你阵营的首领是谁”。哈羊羊说道:“我是喜门的,我的首领是谁我忘了,不过我知道我的上层是谁,让我问问我的上层首领是谁”。于是哈羊羊问了他的上层,他的上层又问了上层,最后通知到了喜羊羊这里,喜羊羊又往下通报确认哈羊羊的身份,最后乐羊羊确认了哈羊羊的身份,并且把哈羊羊当作是自己人。
喜羊羊和沸羊羊大战一场,突然一条情报传入到他们的耳中:“报告门主,美门门主美羊羊被灰太狼抓走了,请求支援!”喜羊羊和沸羊羊一听,立感不妙,现在不是内战的时候,要去救援美羊羊,为了防止内战,于是两羊商量,决定选出一羊作为另一只羊的上层,这样喜门和沸门就完成了合并过程,双方的羊在交战前再次询问上层的时候,都会是喜羊羊或者沸羊羊。
这就是一个简单的“查”和“并”的过程。并查集的关键就是这两个过程。
定义以下的find函数。p是一个数组,用于记录每一个人的上层是谁。当一个人的上层就是自己的时候,那这个人就是门派老大。
int find(int x){while(p[x] != x){x = p[x];}return x;
}
定义以下的join函数,用于将两个元素归为一类。
void join(int x,int y){int fx=find(x), fy=find(y); //喜门1羊的老大是喜羊羊 沸门1号的老大是沸羊羊if(fx != fy) // 如果他们的老大不同p[fx]=fy; //把喜门1号的老大的老大改为沸羊羊 也就是喜羊羊的老大改为沸羊羊
}
现在我们来解答题目。
class Solution {public int [] p = new int[201];public int find(int x){while(p[x] != x){x = p[x];}return x;}public void join(int x,int y){int px = find(x);int py = find(y);if(px != py){p[px] = py;}}public int findCircleNum(int[][] isConnected) {int m = isConnected.length;int n = isConnected[0].length;for(int i = 0;i<p.length;i++){p[i] = i;}for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){if(isConnected[i][j] == 1 && i != j){join(i,j);}}}HashSet<Integer> set = new HashSet<>();for(int i = 0;i<m;i++){set.add(find(p[i]));}return set.size();}
}
上边用到了HashSet结构,HashSet结构不允许有重复值,对于我们的p数组,我们去查找每一个人的门主是谁然后把门主添加到set中,最后进行一个去重,剩下来的就是门主的个数,他们无法合并到一起。对于题目来说就是省份的个数。题目中只有connected为1的两个城市,我们进行join操作。
可见效率有多低。
三、优化find方法
我们之前的找老大的方法是层层向上,但是想一想,一个门派的所有老大只有一个人,如果我们把每个人的上层都改为门主的话,是不是就十分的方便了呢?
int find(int x){//如果x的上层不是门主,那么就接着查找这个人上层的老大if(p[x] != x) p[x] = find(p[x]); //查找老大的时候顺便将这个人的上层的老大修改为门主return p[x];
}
再来看看结果。
代码。
class Solution {public int [] p = new int[201];public int find(int x){if(p[x] != x) p[x] = find(p[x]); //查找老大的时候顺便将这个人的上层的老大全部修改为门主return p[x];}public void join(int x,int y){int px = find(x);int py = find(y);if(px != py){p[px] = py;}}public int findCircleNum(int[][] isConnected) {int m = isConnected.length;int n = isConnected[0].length;for(int i = 0;i<p.length;i++){p[i] = i;}for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){if(isConnected[i][j] == 1 && i != j){join(i,j);}}}HashSet<Integer> set = new HashSet<>();for(int i = 0;i<m;i++){set.add(find(p[i]));}return set.size();}
}
这篇关于【LeetCode】LeetCode 547. 省份数量(Java版 什么是并查集)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!