200. 岛屿数量
题目描述:
给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
1 | 输入: |
示例 2:
1 | 输入: |
解题思路:
该题与695 题取最大的连通面积差不多,只是这个求的是岛屿个数
我们采用广度遍历搜索的思想,还是将二维数组进行循环遍历
本题考点在于 遍历数组时如何深度遍历,也就是如何将所有的指定规则相连的值统计下来。
我们先将 二维数组 grid 进行遍历
如果 gird[ i ] [ j ] 的值为0,continue
如果 gird[ i ] [ j ] 的值为‘1’,将其加入队列中,检测其上下左右方向是否存在1,存在则添加进队列。
注意:遍历连接岛屿时,应将其值设置为‘0’,防止多次遍历查询
第二种解法: 将队列换成递归,在递归中将值设为‘0’,递归完让岛屿数量加+1,也是可以的,终止条件就是 值的坐标大于 x,y长度的边界或者值为‘0’
第三种解法:并查集,这种第一时间是没有想到的,我们遍历二维数组,将值为 ‘1’的作为父节点,查询连接的子节点,将其值设置为父节点的值,注意压缩路径,减少检索时间。
3种解法的时空复杂度 都是 O(m*n) 级别;
解题代码:
第一种:队列、广度优先搜索
1 | private class Node { |
第二种: 递归、深度优先搜索
1 | class Solution { |
第三种解法: 并查集
并查集做法其实与深度遍历差不多,我们只是把并查集的这种数据结构替换了原来的以数组的结构,以及统计时的不一样罢了,大家可以尝试一下。我这里也有相关并查集的介绍和一些并查集的题目。