左神学习笔记-岛屿数量问题(java版算法)
目录
- 1. 问题描述
- 2. 解决方法
- 3. 拓展进阶问题
- 4. 参考链接
1. 问题描述
题目:一个矩阵中只有0和1两个值,每个位置都可以和自己的上下左右
四个位置相连,如果有一片1连在一起,这一部分叫做一个岛,求一个矩阵中有多少岛?
0 0 0 0 0 0 0 0
1 0 0 1 0 1 1 1
1 0 0 1 0 1 0 0
1 0 0 1 0 1 0 0
1 1 1 1 0 0 1 1
0 0 0 0 0 0 0 0
总共有三个岛
2. 解决方法
我们使用感染的方法进行解决
思路:首先遍历数组,遇到1
的话,对其进行感染,判断其上下左右是否有1
,将其变为2
,随后对周围的1
进行感染,直到周围没有1
,进行向下遍历,循环该步骤,直到全部遍历完成。
编写代码:
public class Code03_Islands {public static int countIslands(int[][] m){if(m == null || m[0] == null){return 0;}int N = m.length;int M = m[0].length;int res = 0;for(int i = 0; i < N; i++){for(int j = 0; j < M; j++){if(m[i][j] == 1){res ++;infect(m,i,j,N,M);}}}return res;}// 感染函数public static void infect(int[][] m, int i, int j, int N, int M){// 我不是岛,进行返回if(i < 0|| i >= N || j < 0 || j >= M || m[i][j] != 1){return;}// 设置为不能再次被遍历m[i][j] = 2;// 进行判断infect(m, i + 1, j, N, M);infect(m, i - 1, j, N, M);infect(m, i, j + 1, N, M);infect(m, i, j - 1, N, M);}public static void main(String[] args){int[][] m1 = {{0, 0, 1, 0, 0, 0, 0, 0},{0, 1, 1, 0, 0, 1, 1, 0}};System.out.println(countIslands(m1));}
}
3. 拓展进阶问题
如何设计一个并行算法解决这个问题?
意思是,如果你有两个cpu来处理这个问题,对这个数组进行遍历,如何计算岛的个数
0 0 0 0 0 0 0 0
1 0 0 1 0 1 1 1 这部分由cpu1处理
1 0 0 1 0 1 0 0
-----------------
1 0 0 1 0 1 0 0
1 1 1 1 0 0 1 1 这部分由cpu2处理
0 0 0 0 0 0 0 0
我们可以直观的看出这是三个岛,但是分给两个cpu进行计算的话,上半部分单独给cpu1进行计算的话,就得到数量3,下半部分单独给cpu2进行计算的话,也就得到数量3,该如何得到正确的数量呢?
这里我们使用并查集的方法进行计算,判断他们的根是否相同。
并查集的知识在这里就不进行科普了,后面放几个链接供大家学习。
通过画图,cpu1会得到三个树,cpu2会得到三个树,我们使用并查集对其进行判断,判断树与树是否相接,如果相接,就划分到一个集合,最后查看有几个集合,就能判断有多少个岛了。
4. 参考链接
【算法与数据结构】—— 并查集
并查集
一周刷爆LeetCode,算法大神左神(左程云)耗时100天打造算法与数据结构基础到高级全家桶教程,直击BTAJ等一线大厂必问算法面试题真题详解(马士兵)