教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇技术指南以「算法通关手册」项目中的 0305. 岛屿数量 II 题解 为主体讲解如何用并查集Union Find在二维网格上动态维护岛屿连通性并实时统计岛屿数量。读者学完后将掌握动态加边、实时计数的并查集实战套路包括二维坐标到一维索引的映射、四方向邻域合并、路径压缩与按秩合并的工程实现并能独立解决同类动态连通分量计数问题。一、题目概述1.1 题目背景本题属于「算法通关手册」题解库 0300-0399 分类下的困难题标签为并查集、数组、哈希表。描述给定一个大小为 $m \times n$ 的二维二进制网格 $grid$。网格表示一个地图其中$0$ 表示水$1$ 表示陆地。最初$grid$ 中的所有单元格都是水单元格即所有单元格都是 $0$。可以通过执行addLand操作将某个位置的水转换成陆地。给你一个数组 $positions$其中 $positions[i] [ri, ci]$ 是要执行第 $i$ 次操作的位置 $(ri, ci)$。要求返回一个整数数组 $answer$其中 $answer[i]$ 是将单元格 $(ri, ci)$ 转换为陆地后地图中岛屿的数量。说明岛屿指的是被「水」包围的「陆地」通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。$1 \le m, n, positions.length \le 10^{4}$。$1 \le m \times n \le 10^{4}$。$positions[i].length 2$。$0 \le ri \lt m$。$0 \le ci \lt n$。进阶你可以设计一个时间复杂度 $O(k \log(mn))$ 的算法解决此问题吗其中 $k positions.length$。1.2 示例分析示例 1输入m 3, n 3, positions [[0,0],[0,1],[1,2],[2,1]] 输出[1,1,2,3] 解释 起初二维网格 grid 被全部注入「水」。0 代表「水」1 代表「陆地」 - 操作 #1addLand(0, 0) 将 grid[0][0] 的水变为陆地。此时存在 1 个岛屿。 - 操作 #2addLand(0, 1) 将 grid[0][1] 的水变为陆地。此时存在 1 个岛屿。 - 操作 #3addLand(1, 2) 将 grid[1][2] 的水变为陆地。此时存在 2 个岛屿。 - 操作 #4addLand(2, 1) 将 grid[2][1] 的水变为陆地。此时存在 3 个岛屿。示例 2输入m 1, n 1, positions [[0,0]] 输出[1]从示例 1 可以看出一个关键细节操作 #1 与操作 #2 添加的两块陆地上下相邻因此合并为同一个岛屿岛屿数量仍为 1而操作 #3、#4 添加的陆地与已有岛屿不相邻各自形成独立岛屿所以数量依次递增。这正是本题动态连通性的本质。二、解题思路并查集Union Find2.1 为什么选并查集本题与静态的「岛屿数量」问题不同——网格最初全为水陆地是逐个按位置添加的每次添加后都要实时回答当前有几个岛屿。若每次都用 BFS/DFS 全图扫描代价过高。而岛屿的定义恰好是「被水包围、上下左右相邻的陆地连通块」这天然对应不相交集合的合并与查询每次新增一块陆地先让它自成一个集合岛屿数量 1再检查它上下左右四个方向如果相邻位置已经是陆地就把两个集合合并岛屿数量 -1合并后集合的个数就是当前岛屿数量。这正是「算法通关手册」在 并查集基础教程 中总结的核心能力高效判断两个元素是否属于同一集合、高效合并两个集合并在此基础上扩展出统计集合个数的能力。2.2 算法设计四要素初始化创建大小为 $m \times n$ 的并查集初始时所有位置都是水不属于任何岛屿。添加陆地对每个位置 $(r_i, c_i)$将位置 $(r_i, c_i)$ 标记为陆地并让它自成一个连通分量检查四个方向 $(r_i-1, c_i)$、$(r_i1, c_i)$、$(r_i, c_i-1)$、$(r_i, c_i1)$ 是否已有陆地如果相邻位置已是陆地则与当前新添加的陆地合并到同一个连通分量中统计当前连通分量的数量并记录。坐标转换将二维坐标 $(r, c)$ 转换为一维索引 $index r \times n c$便于并查集基于数组的操作。岛屿计数每次添加陆地后统计并查集中独立连通分量的数量。其中第 3 点是实现层面的关键技巧并查集基于一维数组实现而网格是二维的因此必须建立二维坐标 ↔ 一维索引的映射关系。只要保证r、c满足 $0 \le r \lt m$、$0 \le c \lt n$r * n c就能唯一对应一个网格单元格且不会越界。2.3 完整代码实现以下代码完整继承自原题解文档并补充了逐行注释class UnionFind: def __init__(self, n): 初始化并查集 self.parent [i for i in range(n)] # 父节点数组 self.rank [0] * n # 秩数组用于路径压缩优化 self.count 0 # 连通分量数量 def find(self, x): 查找根节点带路径压缩 if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[x] def union(self, x, y): 合并两个节点 root_x self.find(x) root_y self.find(y) if root_x root_y: return False # 已经在同一个连通分量中 # 按秩合并 if self.rank[root_x] self.rank[root_y]: self.parent[root_x] root_y elif self.rank[root_x] self.rank[root_y]: self.parent[root_y] root_x else: self.parent[root_y] root_x self.rank[root_x] 1 self.count - 1 # 合并后连通分量数量减 1 return True def add_island(self, x): 添加一个新的岛屿 if self.parent[x] ! x: # 已经是陆地 return self.parent[x] x self.count 1 # 新增一个连通分量 class Solution: def numIslands2(self, m: int, n: int, positions: List[List[int]]) - List[int]: 使用并查集解决岛屿数量 II 问题 # 方向数组上、下、左、右 directions [(-1, 0), (1, 0), (0, -1), (0, 1)] # 初始化并查集 uf UnionFind(m * n) # 标记哪些位置是陆地 is_land [False] * (m * n) result [] for r, c in positions: # 将二维坐标转换为一维索引 index r * n c # 如果该位置已经是陆地直接返回当前岛屿数量 if is_land[index]: result.append(uf.count) continue # 标记为陆地 is_land[index] True uf.add_island(index) # 检查四个方向合并相邻的陆地 for dr, dc in directions: new_r, new_c r dr, c dc # 检查边界 if 0 new_r m and 0 new_c n: new_index new_r * n new_c # 如果相邻位置是陆地进行合并 if is_land[new_index]: uf.union(index, new_index) # 记录当前岛屿数量 result.append(uf.count) return result2.4 代码要点解读add_island与union配合维护count每新增一块陆地先count 1每成功合并一次相邻陆地就count - 1。这样uf.count始终精确等于当前岛屿数量避免了每次操作后重新遍历全图统计的额外开销。这相当于在经典并查集基础上扩展了集合计数能力与 并查集基础教程 第 5 节根据具体需求对实现进行适当扩展的建议完全一致。is_land布尔数组并查集的parent数组本身无法区分水与陆地初始时所有位置parent[i] i与未添加的陆地状态一致因此需要独立的is_land数组记录哪些位置已变为陆地只有已标记为陆地的相邻位置才参与合并。重复位置的处理positions中可能出现重复坐标此时该位置已是陆地直接返回当前count避免重复add_island造成计数错误。边界检查四方向扩展时用0 new_r m and 0 new_c n保证不越界这也是地图四周被水包围假设在代码层面的落实。三、并查集底层原理与仓库源码印证本题的解法建立在并查集数据结构之上。「算法通关手册」不仅在题解中给出实现还在 并查集基础教程 中系统讲解了并查集的定义、两种实现思路快速查询的数组实现、快速合并的森林实现、路径压缩与按秩合并仓库 并查集源码 给出了可复用的工程实现。3.1 森林实现与路径压缩题解代码中的find采用递归完全压缩在查找根节点的过程中把路径上经过的所有节点直接挂到根节点下从而显著降低树的高度。仓库中的 tree_unionFind.py 则展示了工程上更推荐的隔代压缩迭代写法def find(self, x): while self.fa[x] ! x: self.fa[x] self.fa[self.fa[x]] # 隔代压缩优化 x self.fa[x] return x两种写法效果等价都保证了后续查找接近 $O(1)$ 均摊代价。按 并查集基础教程 的建议刷题时可优先采用代码更简洁的隔代压缩本题题解采用完全压缩 按秩合并的组合是一种更稳健的工程写法。3.2 按秩合并题解代码中的union采用按深度合并Union By Rank合并时比较两个根节点的rank将秩较小的树根挂到秩较大的树根下深度相同时任选一方为新根并将rank 1。这与仓库中的 tree_unionFind_UnoinByRank.py 实现思路一致。按秩合并的意义在于仅靠路径压缩无法控制整棵树的高度增长而按秩合并能从合并策略上抑制树退化二者结合可以保证并查集操作接近 $O(1)$ 的均摊复杂度。需要注意路径压缩后rank不再代表真实树高它只是合并时比较集合大小的辅助标记正如教程第 3.3 节所强调的不需要维护真实值只要rank能反映两集合的相对大小即可。四、复杂度分析时间复杂度$O(k \times \alpha(mn))$其中 $k$ 是 $positions$ 的长度$\alpha$ 是反阿克曼函数可以认为是常数。每次操作需要检查四个方向并进行并查集操作。在同时使用路径压缩与按秩合并后单次find/union的均摊代价接近 $O(1)$因此总复杂度为 $O(k \times \alpha(mn))$满足题目进阶要求 $O(k \log(mn))$ 的上界。空间复杂度$O(mn)$用于存储并查集的父节点数组、秩数组和陆地标记数组。五、与「岛屿数量 I」的对比「算法通关手册」中收录了这道题的前作 0200. 岛屿数量中等。两者核心区别在于对比维度0200 岛屿数量 I0305 岛屿数量 II网格状态初始给定完整的 0/1 网格初始全为水陆地逐个动态添加询问方式静态求一次岛屿总数每次添加后实时返回岛屿数量常用解法DFS/BFS 全图遍历也可并查集并查集动态维护连通分量难度中等困难可以说本题是把并查集动态合并 实时计数能力发挥到极致的经典题目也是理解离线 DFS与在线并查集两种处理连通性问题思路差异的最佳样例。六、举一反三相关练习本题属于「算法通关手册」并查集题目列表 中的重要成员。掌握本题的套路后可以继续练习同系列题目巩固并查集的动态连通性应用0990. 等式方程的可满足性先合并所有等式、再检验不等式的经典先并后查模型0547. 省份数量统计无向图中连通分量数量0684. 冗余连接在加边过程中检测成环1319. 连通网络的操作次数连通分量计数与补边需求计算0323. 无向图中连通分量的数目更纯粹的连通分量统计。这些题目与本题共享并查集维护连通分量数量这一核心思想反复练习后即可将并查集内化为解决图连通性问题的首选武器。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 305 动态岛屿计数用并查集Union-Find优雅解决 Number of Islands IILeetCode 305 动态岛屿计数用并查集Union Find优雅解决 Number of Islands II 本篇技术指南围绕 articles/CMS后端前端AlgoNote 算法通关手册LeetCode 0213 打家劫舍 II 环形数组动态规划题解AlgoNote 算法通关手册LeetCode 0213 打家劫舍 II 环形数组动态规划题解 本文是「算法通关手册」AlgoNote中 LeetCode教程文档知识库LeetCode 163「缺失的区间」题解线性扫描法详解AlgoNote 算法通关手册LeetCode 163「缺失的区间」题解线性扫描法详解AlgoNote 算法通关手册 导读 本文基于 AlgoNote「算法通关手册」的 0163. 缺教程文档知识库上一篇虚拟化世界的通行证VMware Workstation Pro 17 密钥宝典下一篇wx_channels_download 调试配置指南error 错误捕获与 echolog 代理日志详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考