力扣解题-200. 岛屿数量

力扣解题-200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例 1：
输入：grid = [
[‘1’,‘1’,‘1’,‘1’,‘0’],
[‘1’,‘1’,‘0’,‘1’,‘0’],
[‘1’,‘1’,‘0’,‘0’,‘0’],
[‘0’,‘0’,‘0’,‘0’,‘0’]
]
输出：1

示例 2：
输入：grid = [
[‘1’,‘1’,‘0’,‘0’,‘0’],
[‘1’,‘1’,‘0’,‘0’,‘0’],
[‘0’,‘0’,‘1’,‘0’,‘0’],
[‘0’,‘0’,‘0’,‘1’,‘1’]
]
输出：3

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

Related Topics
深度优先搜索、广度优先搜索、并查集、数组、矩阵

第一次解答

解题思路

核心方法：深度优先搜索（DFS）淹没法，遍历网格中的每个位置，发现陆地（‘1’）时计数+1，并通过DFS将该陆地及其所有相邻的陆地“淹没”（置为’0’），确保每块岛屿仅被计数一次，时间复杂度O(m×n)、空间复杂度O(m×n)（最坏情况全为陆地，递归栈深度达m×n），是本题最直观、易实现的经典解法。

核心逻辑拆解

计算岛屿数量的核心是“发现一块陆地，就标记其所有连通陆地为已访问”，避免重复计数：

1. 空网格处理：若网格为null或行数为0，直接返回0（无岛屿）；
2. 初始化变量：
   • m/n：记录网格的行数和列数，方便后续边界判断；
   • count：岛屿计数器，初始为0；
3. 网格遍历：双重循环遍历每个网格位置(i,j)：
   • 若当前位置是陆地（grid[i][j] == '1'）：
     • 计数器count++（找到新岛屿）；
     • 调用DFS方法，将该陆地及其所有上下左右连通的陆地全部置为’0’（“淹没”，标记为已访问）；
4. DFS核心逻辑（淹没连通陆地）：
   • 递归终止条件：坐标越界（i<0/j<0/i>=m/j>=n）或当前位置不是陆地（grid[i][j] != '1'）；
   • 淹没当前陆地：将grid[i][j]置为’0’，避免重复访问；
   • 递归遍历上下左右四个方向：继续淹没相邻的陆地。

执行流程可视化（以示例2为例）

关键细节说明

• 原地修改网格：直接将访问过的陆地置为’0’，无需额外的访问标记数组，节省空间；
• 边界判断顺序：DFS中先判断坐标越界，再判断网格值，避免数组下标越界异常；
• 连通方向：仅考虑上下左右四个方向（题目明确“水平/竖直相邻”，不包含对角线）；
• 递归终止条件：必须同时判断越界和非陆地，缺一不可（如越界位置无需处理，非陆地直接返回）。

性能说明

• 时间复杂度：O(m×n)（每个网格位置仅被访问一次，DFS过程中被淹没的陆地不会重复处理）；
• 空间复杂度：O(m×n)（最坏情况网格全为陆地，递归栈深度等于网格总元素数；平衡场景下为O(min(m,n))）；
• 优势：
  1. 逻辑直观，贴合“找连通区域”的问题本质；
  2. 原地修改网格，空间效率高；
  3. 代码简洁，仅需基础DFS框架即可实现。

publicintnumIslands(char[][]grid){if(grid==null||grid.length==0){return0;}intm=grid.length;intn=grid[0].length;intcount=0;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]=='1'){count++;//找到岛屿dfs(grid,i,j);//将岛屿淹没}}}returncount;}publicvoiddfs(char[][]grid,inti,intj){if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]!='1'){return;}grid[i][j]='0';//递归访问上下左右四个方向dfs(grid,i-1,j);//上dfs(grid,i+1,j);//下dfs(grid,i,j-1);//左dfs(grid,i,j+1);//右}

示例解答

解题思路

解法1：广度优先搜索（BFS）法（避免递归栈溢出）

核心方法：用队列替代递归实现连通区域的遍历，发现陆地后通过BFS将其所有相邻陆地淹没，逻辑与DFS一致，但避免了递归栈溢出风险（如超大网格场景）。

代码实现

publicintnumIslands(char[][]grid){if(grid==null||grid.length==0){return0;}intm=grid.length;intn=grid[0].length;intcount=0;// 定义上下左右四个方向的偏移量int[][]dirs={{-1,0},{1,0},{0,-1},{0,1}};for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]=='1'){count++;// 队列存储坐标，用数组或自定义类封装Queue<int[]>queue=newLinkedList<>();queue.offer(newint[]{i,j});grid[i][j]='0';// 入队时立即标记为已访问，避免重复入队// BFS遍历连通区域while(!queue.isEmpty()){int[]curr=queue.poll();intx=curr[0];inty=curr[1];// 遍历四个方向for(int[]dir:dirs){intnx=x+dir[0];intny=y+dir[1];// 边界判断+陆地判断if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]=='1'){queue.offer(newint[]{nx,ny});grid[nx][ny]='0';// 入队时标记，避免重复处理}}}}}}returncount;}

核心逻辑说明

1. 方向偏移量：用dirs数组统一管理上下左右四个方向，简化代码；
2. 队列存储坐标：用int[]封装网格坐标，入队时立即将陆地置为’0’，避免同一位置多次入队；
3. BFS循环：队列非空时，持续弹出当前坐标，遍历四个方向，将符合条件的陆地入队并标记。

性能说明

• 时间复杂度：O(m×n)（与DFS一致）；
• 空间复杂度：O(min(m,n))（最坏情况队列存储一行/一列的所有陆地，如网格为长条形陆地）；
• 优势：
  1. 非递归实现，避免超大网格导致的栈溢出；
  2. 队列的空间复杂度通常低于DFS的递归栈；
• 劣势：代码量略多于DFS，需管理队列和坐标封装。

解法2：并查集（Union-Find）法（适合动态连通性场景）

核心方法：将每个陆地位置视为一个节点，相邻陆地合并为同一个集合，最终统计集合的数量即为岛屿数，适合需要频繁查询/修改连通性的进阶场景。

代码实现

classUnionFind{privateintcount;// 连通分量数量privateint[]parent;privateint[]rank;// 按秩合并，优化效率publicUnionFind(char[][]grid){intm=grid.length;intn=grid[0].length;parent=newint[m*n];rank=newint[m*n];count=0;// 初始化并查集for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]=='1'){parent[i*n+j]=i*n+j;// 父节点指向自己count++;// 初始每个陆地都是独立集合}rank[i*n+j]=0;}}}// 查找根节点（路径压缩）publicintfind(intx){if(parent[x]!=x){parent[x]=find(parent[x]);}returnparent[x];}// 合并两个集合（按秩合并）publicvoidunion(intx,inty){introotX=find(x);introotY=find(y);if(rootX!=rootY){if(rank[rootX]>rank[rootY]){parent[rootY]=rootX;}elseif(rank[rootX]<rank[rootY]){parent[rootX]=rootY;}else{parent[rootY]=rootX;rank[rootX]++;}count--;// 合并后连通分量数-1}}publicintgetCount(){returncount;}}publicintnumIslands(char[][]grid){if(grid==null||grid.length==0){return0;}intm=grid.length;intn=grid[0].length;UnionFinduf=newUnionFind(grid);int[][]dirs={{1,0},{0,1}};// 仅需检查下、右两个方向，避免重复合并for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]=='1'){// 遍历下、右方向，合并相邻陆地for(int[]dir:dirs){intnx=i+dir[0];intny=j+dir[1];if(nx<m&&ny<n&&grid[nx][ny]=='1'){uf.union(i*n+j,nx*n+ny);}}}}}returnuf.getCount();}

核心逻辑说明

1. 坐标映射：将二维坐标(i,j)映射为一维索引i*n + j，方便并查集存储；
2. 并查集初始化：每个陆地节点的父节点指向自己，初始连通分量数为陆地总数；
3. 合并相邻陆地：遍历每个陆地，仅检查下、右两个方向（避免重复合并上、左方向），将相邻陆地合并为同一集合；
4. 结果统计：最终连通分量数即为岛屿数。

性能说明

• 时间复杂度：O(m×n×α(m×n))（α为阿克曼函数的反函数，接近常数，可视为O(m×n)）；
• 空间复杂度：O(m×n)（存储parent和rank数组）；
• 优势：
  1. 适合动态连通性场景（如频繁添加/删除陆地后查询岛屿数）；
  2. 路径压缩+按秩合并，效率接近线性；
• 劣势：
  1. 代码实现复杂，新手入门门槛高；
  2. 一次性查询场景下，效率略低于DFS/BFS。

总结

1. DFS淹没法（第一次解答）：O(m×n)时间+O(m×n)空间，逻辑直观、代码简洁，是新手入门的首选解法；
2. BFS法：O(m×n)时间+O(min(m,n))空间，非递归实现，避免栈溢出，适合超大网格场景；
3. 并查集法：O(m×n×α(m×n))时间+O(m×n)空间，适合动态连通性场景，工程拓展性强；
4. 关键技巧：
   • 核心思想：岛屿数量=连通陆地集合的数量，核心是“标记已访问的陆地”避免重复计数；
   • 空间优化：DFS/BFS可原地修改网格，无需额外标记数组；
   • 方向优化：并查集仅需检查下、右方向，减少重复合并操作。