LeetCode200.岛屿数量

问题描述

给你一个由 ‘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

算法原理

这个问题可以通过**并查集（Union-Find）**数据结构高效解决。核心思路是将每个陆地格子视为一个节点，通过相邻关系进行合并操作，最终统计连通分量的数量。

核心思想

1. 二维坐标映射 ：将二维网格的每个格子映射到一维数组（ index = row * cols + col ）
2. 并查集操作 ：遍历所有陆地格子，将相邻的陆地合并到同一个集合
3. 统计结果 ：最终连通分量的数量就是岛屿的数量

Python 实现代码

from typing import List class Solution: def numIslands(self, grid: List[List[str]]) -> int: """ 计算岛屿数量 参数: grid: 二维网格，'1'表示陆地，'0'表示水 返回: 岛屿的数量 """ if not grid or not grid[0]: return 0 n = len(grid) # 行数 m = len(grid[0]) # 列数 # 初始化并查集 father = {} # 父节点字典 sets = 0 # 岛屿数量 def index(a: int, b: int) -> int: """将二维坐标映射到一维索引""" return a * m + b def find(i: int) -> int: """查找节点的根节点（带路径压缩）""" if i != father[i]: father[i] = find(father[i]) # 路径压缩 return father[i] def union(a: int, b: int, c: int, d: int) -> None: """合并两个陆地格子""" nonlocal sets fx = find(index(a, b)) fy = find(index(c, d)) if fx != fy: father[fx] = fy sets -= 1 # 合并后岛屿数量减1 # 初始化：每个陆地格子自成一个集合 for i in range(n): for j in range(m): if grid[i][j] == '1': idx = index(i, j) father[idx] = idx sets += 1 # 遍历所有格子，合并相邻的陆地 for i in range(n): for j in range(m): if grid[i][j] == '1': # 检查左边 if j > 0 and grid[i][j - 1] == '1': union(i, j, i, j - 1) # 检查上边 if i > 0 and grid[i - 1][j] == '1': union(i, j, i - 1, j) return sets

执行流程详解

示例 1 分析

grid = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ]

1. 初始化阶段

m = 5 # 列数 father = {} # 父节点字典 sets = 0 # 初始岛屿数量为0

2. 初始化并查集

遍历所有格子，为每个陆地格子创建独立的集合：

# 第一行 (i=0) grid[0][0] = '1' → father[0] = 0, sets = 1 grid[0][1] = '1' → father[1] = 1, sets = 2 grid[0][2] = '1' → father[2] = 2, sets = 3 grid[0][3] = '1' → father[3] = 3, sets = 4 grid[0][4] = '0' → 跳过 # 第二行 (i=1) grid[1][0] = '1' → father[5] = 5, sets = 5 grid[1][1] = '1' → father[6] = 6, sets = 6 grid[1][2] = '0' → 跳过 grid[1][3] = '1' → father[8] = 8, sets = 7 grid[1][4] = '0' → 跳过 # 第三行 (i=2) grid[2][0] = '1' → father[10] = 10, sets = 8 grid[2][1] = '1' → father[11] = 11, sets = 9 grid[2][2] = '0' → 跳过 grid[2][3] = '0' → 跳过 grid[2][4] = '0' → 跳过 # 第四行 (i=3) 全部是'0'，跳过

初始化完成后 ： sets = 9 （共有 9 个陆地格子）

3. 合并相邻陆地

第一次循环 (i=0, j=0)

grid[0][0] = '1' # 检查左边：j > 0 不成立，跳过 # 检查上边：i > 0 不成立，跳过

第二次循环 (i=0, j=1)

grid[0][1] = '1' # 检查左边：grid[0][0] = '1' → union(0, 1, 0, 0) find(1) → 1, find(0) → 0 father[1] = 0, sets = 8

第三次循环 (i=0, j=2)

grid[0][2] = '1' # 检查左边：grid[0][1] = '1' → union(0, 2, 0, 1) find(2) → 2, find(1) → find(0) → 0 father[2] = 0, sets = 7

第四次循环 (i=0, j=3)

grid[0][3] = '1' # 检查左边：grid[0][2] = '1' → union(0, 3, 0, 2) find(3) → 3, find(2) → find(0) → 0 father[3] = 0, sets = 6

第五次循环 (i=1, j=0)

grid[1][0] = '1' # 检查左边：j > 0 不成立，跳过 # 检查上边：grid[0][0] = '1' → union(1, 0, 0, 0) find(5) → 5, find(0) → 0 father[5] = 0, sets = 5

第六次循环 (i=1, j=1)

grid[1][1] = '1' # 检查左边：grid[1][0] = '1' → union(1, 1, 1, 0) find(6) → 6, find(5) → find(0) → 0 father[6] = 0, sets = 4 # 检查上边：grid[0][1] = '1' → union(1, 1, 0, 1) find(6) → find(0) → 0, find(1) → find(0) → 0 已经在同一集合，跳过

后续循环

• 所有剩余的陆地格子都会通过 find 操作找到根节点 0
• 最终所有陆地格子都合并到同一个集合

4. 计算结果

return sets = 1

关键技术点解析

1. 二维坐标映射

def index(a: int, b: int) -> int: return a * m + b

• 将二维坐标 (row, col) 映射到一维索引
• 便于在并查集中使用数组存储

2. 路径压缩优化

def find(i: int) -> int: if i != father[i]: father[i] = find(father[i]) # 路径压缩 return father[i]

• 每次查找时更新父节点，使后续查找更快
• 时间复杂度接近 O(1)

3. 相邻关系判断

# 只检查左边和上边，避免重复合并 if j > 0 and grid[i][j - 1] == '1': union(i, j, i, j - 1) if i > 0 and grid[i - 1][j] == '1': union(i, j, i - 1, j)

• 只需检查两个方向（左和上），避免重复处理
• 因为右和下方向的格子会在后续循环中处理

复杂度分析

• 时间复杂度 ：O(nm α(nm))，其中 n 是行数，m 是列数，α是阿克曼函数的反函数
• 空间复杂度 ：O(nm)，用于存储并查集的父节点数组

总结

通过这个详细的解析，我们可以清晰地看到算法如何将复杂的岛屿计数问题转化为连通分量的计算，从而高效地得到岛屿的数量。并查集数据结构在这个问题中发挥了关键作用，使得我们能够在接近线性的时间复杂度内解决问题。

核心要点 ：

1. 理解二维坐标到一维索引的映射
2. 掌握并查集的基本操作（find 和 union）
3. 理解连通分量数的物理意义
4. 只检查两个方向（左和上）避免重复处理

这个算法不仅适用于岛屿数量问题，还可以推广到其他需要判断连通性的网格问题。