文章目录问题描述示例算法原理核心思想Python 实现代码执行流程详解示例 1 分析1. 初始化阶段2. 初始化并查集3. 合并相邻陆地4. 计算结果关键技术点解析1. 二维坐标映射2. 路径压缩优化3. 相邻关系判断复杂度分析总结问题描述给你一个由 ‘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**数据结构高效解决。核心思路是将每个陆地格子视为一个节点通过相邻关系进行合并操作最终统计连通分量的数量。核心思想二维坐标映射 将二维网格的每个格子映射到一维数组 index row * cols col 并查集操作 遍历所有陆地格子将相邻的陆地合并到同一个集合统计结果 最终连通分量的数量就是岛屿的数量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 # 初始岛屿数量为02. 初始化并查集遍历所有格子为每个陆地格子创建独立的集合# 第一行 (i0) 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 → 跳过 # 第二行 (i1) 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 → 跳过 # 第三行 (i2) 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 → 跳过 # 第四行 (i3) 全部是0跳过初始化完成后 sets 9 共有 9 个陆地格子3. 合并相邻陆地第一次循环 (i0, j0)grid[0][0] 1 # 检查左边j 0 不成立跳过 # 检查上边i 0 不成立跳过第二次循环 (i0, j1)grid[0][1] 1 # 检查左边grid[0][0] 1 → union(0, 1, 0, 0) find(1) → 1, find(0) → 0 father[1] 0, sets 8第三次循环 (i0, j2)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第四次循环 (i0, j3)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第五次循环 (i1, j0)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第六次循环 (i1, j1)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)用于存储并查集的父节点数组总结通过这个详细的解析我们可以清晰地看到算法如何将复杂的岛屿计数问题转化为连通分量的计算从而高效地得到岛屿的数量。并查集数据结构在这个问题中发挥了关键作用使得我们能够在接近线性的时间复杂度内解决问题。核心要点 理解二维坐标到一维索引的映射掌握并查集的基本操作find 和 union理解连通分量数的物理意义只检查两个方向左和上避免重复处理这个算法不仅适用于岛屿数量问题还可以推广到其他需要判断连通性的网格问题。
LeetCode200.岛屿数量
文章目录问题描述示例算法原理核心思想Python 实现代码执行流程详解示例 1 分析1. 初始化阶段2. 初始化并查集3. 合并相邻陆地4. 计算结果关键技术点解析1. 二维坐标映射2. 路径压缩优化3. 相邻关系判断复杂度分析总结问题描述给你一个由 ‘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**数据结构高效解决。核心思路是将每个陆地格子视为一个节点通过相邻关系进行合并操作最终统计连通分量的数量。核心思想二维坐标映射 将二维网格的每个格子映射到一维数组 index row * cols col 并查集操作 遍历所有陆地格子将相邻的陆地合并到同一个集合统计结果 最终连通分量的数量就是岛屿的数量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 # 初始岛屿数量为02. 初始化并查集遍历所有格子为每个陆地格子创建独立的集合# 第一行 (i0) 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 → 跳过 # 第二行 (i1) 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 → 跳过 # 第三行 (i2) 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 → 跳过 # 第四行 (i3) 全部是0跳过初始化完成后 sets 9 共有 9 个陆地格子3. 合并相邻陆地第一次循环 (i0, j0)grid[0][0] 1 # 检查左边j 0 不成立跳过 # 检查上边i 0 不成立跳过第二次循环 (i0, j1)grid[0][1] 1 # 检查左边grid[0][0] 1 → union(0, 1, 0, 0) find(1) → 1, find(0) → 0 father[1] 0, sets 8第三次循环 (i0, j2)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第四次循环 (i0, j3)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第五次循环 (i1, j0)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第六次循环 (i1, j1)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)用于存储并查集的父节点数组总结通过这个详细的解析我们可以清晰地看到算法如何将复杂的岛屿计数问题转化为连通分量的计算从而高效地得到岛屿的数量。并查集数据结构在这个问题中发挥了关键作用使得我们能够在接近线性的时间复杂度内解决问题。核心要点 理解二维坐标到一维索引的映射掌握并查集的基本操作find 和 union理解连通分量数的物理意义只检查两个方向左和上避免重复处理这个算法不仅适用于岛屿数量问题还可以推广到其他需要判断连通性的网格问题。
