1. 一个高频面试题引出的数据机构之争岛屿数量1.1 题目本身到底在考什么LeetCode 200岛屿数量题目描述非常简短给你一个由1陆地和0水组成的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。很多第一次刷题的人会以为这题就是考 DFS深度优先搜索因为递归遍历1周围四个方向遇到1就淹没成0循环统计调用次数似乎几分钟就写完。确实DFS 和 BFS 都能 AC而且代码短。但真正去大厂面试时面试官常常会追加一句你先别急能不能用并查集做一遍这道题能流传得这么广恰恰因为它可以同时考察三种核心思维写的 DFS 考递归熟练度写的 BFS 考队列使用写并查集才是真正考你会不会用数据结构抽象连通性问题。1.2 为什么这种网格连通问题天然适合并查集并查集Union-Find解决的是动态连通性问题也就是两个元素是否属于同一个集合以及把两个集合合并成一个。把网格里的每一块陆地看成一个个独立的节点相邻的陆地之间建立连接关系那么所有互相连通的陆地最终会归属到同一个集合里。一个集合对应一座岛屿统计集合的个数就是统计岛屿数量。这个思路最优雅的地方在于DFS 是靠递归隐式维护连通性而并查集是显式地维护谁和谁连在一起。DFS 适合回答从某个点出发能到达哪些点并查集则更适合回答任意两个点是不是同一个集合里的。岛屿数量这道题要的是总共有几个连通块并查集做这个统计几乎不需要额外思考只要维护一个count变量每次合并成功就减一最后剩下的就是答案。2. 并查集的基础框架三样东西缺一不可2.1 数据结构的核心字段一个朴素的并查集要维护三个字段int[] parent; // 每个节点的父节点初始时指向自己 int[] rank; // 树的秩高度上界用于合并时保持平衡 int count; // 当前连通分量个数即集合总数parent是并查集的主干find(x)不断向上找直到找到parent[x] x的那个节点它就是集合的代表元。count是这道题里最关键的变量初始化为陆地总数每次合并两个不同集合时count--最后count就是岛屿数。2.2 find 操作路径压缩的两种写法find的作用是找到元素所在集合的根节点同时做路径压缩。路径压缩的目的是把树的形状压扁让每个节点尽量直接指向根这样后续查找几乎可以做到 O(1)。递归版本的find是最容易记忆的写法public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; }这里parent[x] find(parent[x])就是路径压缩的体现在递归返回的过程中不断把中间节点直接挂到根节点上。注意虽然递归在极端情况下比如数深度特别大可能有栈溢出的风险但配合路径压缩后树的高度很小实际应用中很少出问题。如果你实在担心可以写迭代版本public int find(int x) { int root x; while (parent[root] ! root) { root parent[root]; } // 第二遍循环把路径上所有节点直接指向根 while (parent[x] ! x) { int next parent[x]; parent[x] root; x next; } return root; }两种写法都可以我更推荐递归版本代码短、可读性强面试时也容易当场写对。2.3 union 操作按秩合并到底秩什么union的核心逻辑很简单先找两个节点各自所在集合的代表元如果代表元相同说明本来就在一个集合里什么都不用做如果不同就把一棵树的根接到另一棵树的根上。问题在于谁接谁如果随便接最坏情况下会形成一条链查找退化成 O(n)。按秩合并的思路是让矮的树接在高的树下面从而保持整体树的高度尽量小。这里的秩在经典实现中通常指树的高度上界当两个秩相同的树合并时新树的秩加一。public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; }在岛屿数量这道题上count的递减非常关键。只有真的发生了合并集合总数才减少如果两个节点本来就在同一个集合里count不能减。3. 岛屿数量并查集完整代码一次 AC 的工程实践3.1 完整可运行的 Java 代码下面是可直接提交到 LeetCode 的完整代码注释几乎可以当作讲解稿来读class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; // 第一步初始化并查集把所有陆地视为独立节点 UnionFind uf new UnionFind(grid); // 第二步遍历每个格子只向右和向下合并避免重复操作 for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { int index i * cols j; // 二维转一维 if (j 1 cols grid[i][j 1] 1) { uf.union(index, index 1); } if (i 1 rows grid[i 1][j] 1) { uf.union(index, index cols); } } } } return uf.getCount(); } // 内部类并查集 class UnionFind { int[] parent; int[] rank; int count; // 岛的数量 public UnionFind(char[][] grid) { int rows grid.length; int cols grid[0].length; parent new int[rows * cols]; rank new int[rows * cols]; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { int index i * cols j; parent[index] index; count; // 每块陆地初始都是一个独立的岛 } else { parent[index] -1; // 水标记为无效节点 } } } } public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; // 只有真正合并岛屿数才减少 } public int getCount() { return count; } } }3.2 代码中的几个别有用心的设计第一个是只向右和向下合并。四方向遍历当然也可以但每个格子都检查上下左右必然导致大量重复操作。比如格子 (0,0) 检查右边 (0,1) 合并了一次等遍历到 (0,1) 时又检查左边 (0,0) 再合并一次虽然 find 会判断出已连接但白白浪费了两次查找的开销。只检查右和下既能保证所有相邻陆地都被合并又消除了冗余。这个优化思路在面试时主动说出来是很加分的。第二个是把二维坐标压缩成一维 ID。公式index i * cols j是网格类并查集问题的核心技巧。一维索引的好处是parent和rank数组不需要开二维代码简洁而且向右合并只需index 1向下合并只需index cols非常直观。第三个是用parent[index] -1标记水域。这样在后续 find 时如果误把水域传进去通过 parent 数组的值能很快发现异常。不过严格来说numIslands 主函数的遍历逻辑只会对grid[i][j] 1的格子调用 union所以 -1 标记更多是防御性编程的意思能帮你第一时间定位 bug。3.3 为什么 count 能准确反映岛屿数量初始化的逻辑是每一块陆地单独算一个岛屿水不算。比如一个 3x3 的全陆地图count 初始化是 9经过 8 次成功的 union 后count 变成 1表示最终只有一个岛。又比如一个全水图count 始终是 0因为循环里根本没有陆地可初始化最后返回 0。关键点在于union 里必须count--且只在两个根不同时递减。如果你把count--放在if (rootX rootY) return;之前逻辑就错了合并同一个集合会把岛屿数减成负数。这种细节非常容易在面试高压状态下写错。4. 手推一遍4x5 网格是怎么从 9 块陆地变成 3 座岛的4.1 模拟初始化过程假设输入是1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1先做初始化。遍历所有格子把 9 块陆地依次建立对应的parent节点parent[i]icount 为 9。二维坐标与一维索引的对应关系是第 0 行第 0 列 - 0第 0 行第 1 列 - 1第 1 行第 0 列 - 4第 1 行第 1 列 - 5第 2 行第 2 列 - 10第 3 行第 3 列 - 15第 3 行第 4 列 - 16。这个坐标到索引的映射是整道题最容易乱的地方我的习惯是先在草稿纸上把网格按一维展开写下每个格子对应的索引再开始手推合并这样不容易出错。4.2 逐次合并过程遍历 (0,0)右边 (0,1) 是陆地合并 0 和 1count 变 8遍历 (0,1)右边 (0,2) 是水下边 (1,1) 是陆地合并 1 和 5count 变 7遍历 (0,2)不是陆地跳过遍历 (1,0)右边 (1,1) 是陆地合并 4 和 5。此时 find(4)4find(5) 会一路找到根 0因为 5 的父节点已经是 0 了合并 4 到 0count 变 6遍历 (1,1)右边 (1,2) 是水下边 (2,1) 是水无操作遍历 (2,2)右边是水下边的 (3,2) 是水无操作遍历 (3,3)右边 (3,4) 是陆地合并 15 和 16count 变 5遍历 (3,4)没有右边和下边无操作。最终 count 等于 5这不对预期应该是 3。等下我再数一遍陆地块数。这个 4x5 网格里的1是左上角 2x2 四块中间 (2,2) 一块右下角 (3,3)(3,4) 两块共 7 块。初始 count 应该是 7不是 9。上面我说 9 是笔误。重新推初始化 count 7。第一次合并 0 和 1 后变 6第二次合并 1 和 5 后变 5第三次合并 4 和 5 后变 4第四次合并 15 和 16 后变 3。最终 count 3也就是左上角岛、正中间岛、右下角岛正确。4.3 路径压缩带来的蝴蝶效应注意上面第三步合并中find(5)的返回值很关键。在第二次合并时我们已经把 1 和 5 合并了而且实现时rank[1]和rank[5]相等所以parent[5] 1同时rank[1]变成 1。到了第三次合并时find(5)先找到 11 的父节点是 0因为第一次合并时parent[1] 0所以 5 的根是 0。路径压缩后5 的父节点直接从 1 改成 0以后任何以 5 为入口的 find 只需两步。如果没有路径压缩树会越并越高find 的代价越来越大。路径压缩加按秩合并两者结合才能保证并查集的操作均摊复杂度接近 O(α(n))其中 α 是反阿克曼函数增长极慢实际可以认为是 O(1)。5. 边界情况与易错点排查实录5.1 空输入与单行单列最容易翻车的不是算法本身而是输入边界。grid为 null、grid.length 0、grid[0].length 0这三种情况都要单独处理代码里直接返回 0 即可。单行网格如{10101}也必须正确处理此时i 1 rows永远为 false只会走向右合并的逻辑最终 count 是 3三块陆地各自成岛正确。单列网格{{1},{1},{0},{1}}同理只走向下合并最终 count 是 2。很多人写这道题时会在grid[0].length上报空指针异常就是因为忽略了grid.length 0的情况。LeetCode 的测试用例有时会直接给你一个空的二维数组稳一点的做法是一开始就做三层判断if (grid null || grid.length 0 || grid[0] null || grid[0].length 0) { return 0; }5.2 第二维长度不一致带来的越界问题我自己在本地测试时遇到过一个问题故意构造了一个不规则的二维数组比如第一行 3 列、第二行 4 列。这类非矩阵输入在 LeetCode 上不会出现但本地测试要小心。本题假定网格是规整的char[][]所有行的列数一致代码里grid[i][j 1]依赖这个假设。所以写测试用例时一定要用规则矩阵否则越界异常会让你误以为算法有 bug。5.3 把水也初始化进并查集有些初学者会把所有格子都初始化成节点包括0的水域然后 union 时只操作陆地。这样 parent 数组里水域节点始终是孤立节点最后数 count 时会把水域也算进去。避免方式就是上面的写法只有陆地才parent[index] index和count水域设为 -1不参与统计。另一种常见的错误写法是在 numIslands 结束后再遍历 parent 数组统计parent[i] i的节点数量这种方法也能得到岛屿数因为水域的 parent 是 -1不算根节点。但这样做的缺陷是如果你把水域节点也初始化成parent[i] i统计就会出错。所以要么统一用 count 变量要么统一用根节点统计法别混用。6. 面试官追问时你能答到什么层级6.1 复杂度分析要讲清楚为什么是 O(MN·α(MN))主函数遍历整个网格是 O(MN)每次 union 和 find 因为路径压缩和按秩合并均摊时间复杂度是 O(α(MN))。α 是反阿克曼函数在人类能遇到的任何输入规模下都不超过 4所以面试时可以直接说近似 O(MN)。但这里有个微妙的点初始化 parent 和 rank 数组要遍历 grid 一次合并又要遍历 grid 一次所以常数项是 2但大 O 还是 O(MN)。空间复杂度方面parent 和 rank 各是 O(MN)加上原本的 grid 是输入不纳入额外空间的话就是 O(MN)。有个细节值得在面试时主动提rank 字段可以省吗可以但合并时退化风险大。理论上只用路径压缩的并查集单次 find 的均摊复杂度已经是 O(log n)实际也够快但配合按秩合并才能达到理论上的 O(α(n))。对于岛屿数量这种只需要最终统计的场景省掉 rank 用随机合并在 LeetCode 的数据量下不会超时但面试官会怀疑你只背了模板、不理解秩的含义。6.2 并查集 vs DFS vs BFS 的对比方面DFSBFS并查集代码量最短中等最长连通性维护隐式隐式显式是否支持动态加边否否是空间复杂度O(MN) 递归栈O(min(M,N)) 队列O(MN) 数组面试加分点简单直接层序遍历思想数据结构运用适合追问场景无路径类问题动态连通、合并类问题实际面试时如果面试官让你用两种方法做我的建议是先讲 DFS 把题目做出来再讲并查集方案最后主动对比DFS 的搜索天然适合回答从一个点出发能到达哪些地方并查集更像维护一张连接关系网。这样既展示基础又展示抽象能力。6.3 并查集在同类问题里的弹药库岛屿数量只是并查集应用的入门把这道题吃透后下面这些题基本可以秒杀LeetCode 130被围绕的区域用并查集把所有边界上的O连到一个虚拟节点再遍历内部O判断是否和虚拟节点连通LeetCode 990等式方程的可满足性先把所有的变量合并再检查!的变量是否在同一集合LeetCode 684冗余连接在无向图中找一条导致成环的边边遍历边 union遇到find相同的两条边就是答案LeetCode 323无向图中连通分量的数量比岛屿数量更直接的并查集应用N 个节点初始 count 就是 N每条边合并一次最后 count 就是答案。这类问题的共同模式是先找节点再找节点之间相邻或关系的定义然后套并查集模板。网格类的节点是一维扩展索引图论类的节点就是 0 到 n-1 的编号本质完全一样。7. 写在最后关于这道题我的真实体会我至少带过 5 个学弟学妹刷这道题自己也重新写过多遍每次都有新感悟。并查集模板本身很固定难点不在实现而在于你能不能在读题 30 秒内意识到这道题是并查集。我的判断方法很简单如果题目里出现了连通分区圈子冗余连接是否属于同一集合这些词优先往并查集想。另外分享一下我在用通义千问等代码辅助工具排查本地测试用例时的习惯先把自己的代码和测试数据喂进去请工具帮忙检查有没有数组越界或逻辑漏洞但核心算法一定自己先想清楚。工具可以帮你节省 debug 时间却不能替你做抽象建模。最后一个小建议不要只满足于 AC。拿出草稿纸把一个 4x5 的网格手动模拟一遍合并过程你才能真切感受到 count 是怎么一步步降下来的。写完并查集版本后再回头写一遍 DFS 版本比较两种思维差异。这样花的一个小时性价比比闷头刷十道新题高得多。
1. 一个高频面试题引出的数据机构之争岛屿数量1.1 题目本身到底在考什么LeetCode 200岛屿数量题目描述非常简短给你一个由1陆地和0水组成的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。很多第一次刷题的人会以为这题就是考 DFS深度优先搜索因为递归遍历1周围四个方向遇到1就淹没成0循环统计调用次数似乎几分钟就写完。确实DFS 和 BFS 都能 AC而且代码短。但真正去大厂面试时面试官常常会追加一句你先别急能不能用并查集做一遍这道题能流传得这么广恰恰因为它可以同时考察三种核心思维写的 DFS 考递归熟练度写的 BFS 考队列使用写并查集才是真正考你会不会用数据结构抽象连通性问题。1.2 为什么这种网格连通问题天然适合并查集并查集Union-Find解决的是动态连通性问题也就是两个元素是否属于同一个集合以及把两个集合合并成一个。把网格里的每一块陆地看成一个个独立的节点相邻的陆地之间建立连接关系那么所有互相连通的陆地最终会归属到同一个集合里。一个集合对应一座岛屿统计集合的个数就是统计岛屿数量。这个思路最优雅的地方在于DFS 是靠递归隐式维护连通性而并查集是显式地维护谁和谁连在一起。DFS 适合回答从某个点出发能到达哪些点并查集则更适合回答任意两个点是不是同一个集合里的。岛屿数量这道题要的是总共有几个连通块并查集做这个统计几乎不需要额外思考只要维护一个count变量每次合并成功就减一最后剩下的就是答案。2. 并查集的基础框架三样东西缺一不可2.1 数据结构的核心字段一个朴素的并查集要维护三个字段int[] parent; // 每个节点的父节点初始时指向自己 int[] rank; // 树的秩高度上界用于合并时保持平衡 int count; // 当前连通分量个数即集合总数parent是并查集的主干find(x)不断向上找直到找到parent[x] x的那个节点它就是集合的代表元。count是这道题里最关键的变量初始化为陆地总数每次合并两个不同集合时count--最后count就是岛屿数。2.2 find 操作路径压缩的两种写法find的作用是找到元素所在集合的根节点同时做路径压缩。路径压缩的目的是把树的形状压扁让每个节点尽量直接指向根这样后续查找几乎可以做到 O(1)。递归版本的find是最容易记忆的写法public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; }这里parent[x] find(parent[x])就是路径压缩的体现在递归返回的过程中不断把中间节点直接挂到根节点上。注意虽然递归在极端情况下比如数深度特别大可能有栈溢出的风险但配合路径压缩后树的高度很小实际应用中很少出问题。如果你实在担心可以写迭代版本public int find(int x) { int root x; while (parent[root] ! root) { root parent[root]; } // 第二遍循环把路径上所有节点直接指向根 while (parent[x] ! x) { int next parent[x]; parent[x] root; x next; } return root; }两种写法都可以我更推荐递归版本代码短、可读性强面试时也容易当场写对。2.3 union 操作按秩合并到底秩什么union的核心逻辑很简单先找两个节点各自所在集合的代表元如果代表元相同说明本来就在一个集合里什么都不用做如果不同就把一棵树的根接到另一棵树的根上。问题在于谁接谁如果随便接最坏情况下会形成一条链查找退化成 O(n)。按秩合并的思路是让矮的树接在高的树下面从而保持整体树的高度尽量小。这里的秩在经典实现中通常指树的高度上界当两个秩相同的树合并时新树的秩加一。public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; }在岛屿数量这道题上count的递减非常关键。只有真的发生了合并集合总数才减少如果两个节点本来就在同一个集合里count不能减。3. 岛屿数量并查集完整代码一次 AC 的工程实践3.1 完整可运行的 Java 代码下面是可直接提交到 LeetCode 的完整代码注释几乎可以当作讲解稿来读class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; // 第一步初始化并查集把所有陆地视为独立节点 UnionFind uf new UnionFind(grid); // 第二步遍历每个格子只向右和向下合并避免重复操作 for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { int index i * cols j; // 二维转一维 if (j 1 cols grid[i][j 1] 1) { uf.union(index, index 1); } if (i 1 rows grid[i 1][j] 1) { uf.union(index, index cols); } } } } return uf.getCount(); } // 内部类并查集 class UnionFind { int[] parent; int[] rank; int count; // 岛的数量 public UnionFind(char[][] grid) { int rows grid.length; int cols grid[0].length; parent new int[rows * cols]; rank new int[rows * cols]; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { int index i * cols j; parent[index] index; count; // 每块陆地初始都是一个独立的岛 } else { parent[index] -1; // 水标记为无效节点 } } } } public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; // 只有真正合并岛屿数才减少 } public int getCount() { return count; } } }3.2 代码中的几个别有用心的设计第一个是只向右和向下合并。四方向遍历当然也可以但每个格子都检查上下左右必然导致大量重复操作。比如格子 (0,0) 检查右边 (0,1) 合并了一次等遍历到 (0,1) 时又检查左边 (0,0) 再合并一次虽然 find 会判断出已连接但白白浪费了两次查找的开销。只检查右和下既能保证所有相邻陆地都被合并又消除了冗余。这个优化思路在面试时主动说出来是很加分的。第二个是把二维坐标压缩成一维 ID。公式index i * cols j是网格类并查集问题的核心技巧。一维索引的好处是parent和rank数组不需要开二维代码简洁而且向右合并只需index 1向下合并只需index cols非常直观。第三个是用parent[index] -1标记水域。这样在后续 find 时如果误把水域传进去通过 parent 数组的值能很快发现异常。不过严格来说numIslands 主函数的遍历逻辑只会对grid[i][j] 1的格子调用 union所以 -1 标记更多是防御性编程的意思能帮你第一时间定位 bug。3.3 为什么 count 能准确反映岛屿数量初始化的逻辑是每一块陆地单独算一个岛屿水不算。比如一个 3x3 的全陆地图count 初始化是 9经过 8 次成功的 union 后count 变成 1表示最终只有一个岛。又比如一个全水图count 始终是 0因为循环里根本没有陆地可初始化最后返回 0。关键点在于union 里必须count--且只在两个根不同时递减。如果你把count--放在if (rootX rootY) return;之前逻辑就错了合并同一个集合会把岛屿数减成负数。这种细节非常容易在面试高压状态下写错。4. 手推一遍4x5 网格是怎么从 9 块陆地变成 3 座岛的4.1 模拟初始化过程假设输入是1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1先做初始化。遍历所有格子把 9 块陆地依次建立对应的parent节点parent[i]icount 为 9。二维坐标与一维索引的对应关系是第 0 行第 0 列 - 0第 0 行第 1 列 - 1第 1 行第 0 列 - 4第 1 行第 1 列 - 5第 2 行第 2 列 - 10第 3 行第 3 列 - 15第 3 行第 4 列 - 16。这个坐标到索引的映射是整道题最容易乱的地方我的习惯是先在草稿纸上把网格按一维展开写下每个格子对应的索引再开始手推合并这样不容易出错。4.2 逐次合并过程遍历 (0,0)右边 (0,1) 是陆地合并 0 和 1count 变 8遍历 (0,1)右边 (0,2) 是水下边 (1,1) 是陆地合并 1 和 5count 变 7遍历 (0,2)不是陆地跳过遍历 (1,0)右边 (1,1) 是陆地合并 4 和 5。此时 find(4)4find(5) 会一路找到根 0因为 5 的父节点已经是 0 了合并 4 到 0count 变 6遍历 (1,1)右边 (1,2) 是水下边 (2,1) 是水无操作遍历 (2,2)右边是水下边的 (3,2) 是水无操作遍历 (3,3)右边 (3,4) 是陆地合并 15 和 16count 变 5遍历 (3,4)没有右边和下边无操作。最终 count 等于 5这不对预期应该是 3。等下我再数一遍陆地块数。这个 4x5 网格里的1是左上角 2x2 四块中间 (2,2) 一块右下角 (3,3)(3,4) 两块共 7 块。初始 count 应该是 7不是 9。上面我说 9 是笔误。重新推初始化 count 7。第一次合并 0 和 1 后变 6第二次合并 1 和 5 后变 5第三次合并 4 和 5 后变 4第四次合并 15 和 16 后变 3。最终 count 3也就是左上角岛、正中间岛、右下角岛正确。4.3 路径压缩带来的蝴蝶效应注意上面第三步合并中find(5)的返回值很关键。在第二次合并时我们已经把 1 和 5 合并了而且实现时rank[1]和rank[5]相等所以parent[5] 1同时rank[1]变成 1。到了第三次合并时find(5)先找到 11 的父节点是 0因为第一次合并时parent[1] 0所以 5 的根是 0。路径压缩后5 的父节点直接从 1 改成 0以后任何以 5 为入口的 find 只需两步。如果没有路径压缩树会越并越高find 的代价越来越大。路径压缩加按秩合并两者结合才能保证并查集的操作均摊复杂度接近 O(α(n))其中 α 是反阿克曼函数增长极慢实际可以认为是 O(1)。5. 边界情况与易错点排查实录5.1 空输入与单行单列最容易翻车的不是算法本身而是输入边界。grid为 null、grid.length 0、grid[0].length 0这三种情况都要单独处理代码里直接返回 0 即可。单行网格如{10101}也必须正确处理此时i 1 rows永远为 false只会走向右合并的逻辑最终 count 是 3三块陆地各自成岛正确。单列网格{{1},{1},{0},{1}}同理只走向下合并最终 count 是 2。很多人写这道题时会在grid[0].length上报空指针异常就是因为忽略了grid.length 0的情况。LeetCode 的测试用例有时会直接给你一个空的二维数组稳一点的做法是一开始就做三层判断if (grid null || grid.length 0 || grid[0] null || grid[0].length 0) { return 0; }5.2 第二维长度不一致带来的越界问题我自己在本地测试时遇到过一个问题故意构造了一个不规则的二维数组比如第一行 3 列、第二行 4 列。这类非矩阵输入在 LeetCode 上不会出现但本地测试要小心。本题假定网格是规整的char[][]所有行的列数一致代码里grid[i][j 1]依赖这个假设。所以写测试用例时一定要用规则矩阵否则越界异常会让你误以为算法有 bug。5.3 把水也初始化进并查集有些初学者会把所有格子都初始化成节点包括0的水域然后 union 时只操作陆地。这样 parent 数组里水域节点始终是孤立节点最后数 count 时会把水域也算进去。避免方式就是上面的写法只有陆地才parent[index] index和count水域设为 -1不参与统计。另一种常见的错误写法是在 numIslands 结束后再遍历 parent 数组统计parent[i] i的节点数量这种方法也能得到岛屿数因为水域的 parent 是 -1不算根节点。但这样做的缺陷是如果你把水域节点也初始化成parent[i] i统计就会出错。所以要么统一用 count 变量要么统一用根节点统计法别混用。6. 面试官追问时你能答到什么层级6.1 复杂度分析要讲清楚为什么是 O(MN·α(MN))主函数遍历整个网格是 O(MN)每次 union 和 find 因为路径压缩和按秩合并均摊时间复杂度是 O(α(MN))。α 是反阿克曼函数在人类能遇到的任何输入规模下都不超过 4所以面试时可以直接说近似 O(MN)。但这里有个微妙的点初始化 parent 和 rank 数组要遍历 grid 一次合并又要遍历 grid 一次所以常数项是 2但大 O 还是 O(MN)。空间复杂度方面parent 和 rank 各是 O(MN)加上原本的 grid 是输入不纳入额外空间的话就是 O(MN)。有个细节值得在面试时主动提rank 字段可以省吗可以但合并时退化风险大。理论上只用路径压缩的并查集单次 find 的均摊复杂度已经是 O(log n)实际也够快但配合按秩合并才能达到理论上的 O(α(n))。对于岛屿数量这种只需要最终统计的场景省掉 rank 用随机合并在 LeetCode 的数据量下不会超时但面试官会怀疑你只背了模板、不理解秩的含义。6.2 并查集 vs DFS vs BFS 的对比方面DFSBFS并查集代码量最短中等最长连通性维护隐式隐式显式是否支持动态加边否否是空间复杂度O(MN) 递归栈O(min(M,N)) 队列O(MN) 数组面试加分点简单直接层序遍历思想数据结构运用适合追问场景无路径类问题动态连通、合并类问题实际面试时如果面试官让你用两种方法做我的建议是先讲 DFS 把题目做出来再讲并查集方案最后主动对比DFS 的搜索天然适合回答从一个点出发能到达哪些地方并查集更像维护一张连接关系网。这样既展示基础又展示抽象能力。6.3 并查集在同类问题里的弹药库岛屿数量只是并查集应用的入门把这道题吃透后下面这些题基本可以秒杀LeetCode 130被围绕的区域用并查集把所有边界上的O连到一个虚拟节点再遍历内部O判断是否和虚拟节点连通LeetCode 990等式方程的可满足性先把所有的变量合并再检查!的变量是否在同一集合LeetCode 684冗余连接在无向图中找一条导致成环的边边遍历边 union遇到find相同的两条边就是答案LeetCode 323无向图中连通分量的数量比岛屿数量更直接的并查集应用N 个节点初始 count 就是 N每条边合并一次最后 count 就是答案。这类问题的共同模式是先找节点再找节点之间相邻或关系的定义然后套并查集模板。网格类的节点是一维扩展索引图论类的节点就是 0 到 n-1 的编号本质完全一样。7. 写在最后关于这道题我的真实体会我至少带过 5 个学弟学妹刷这道题自己也重新写过多遍每次都有新感悟。并查集模板本身很固定难点不在实现而在于你能不能在读题 30 秒内意识到这道题是并查集。我的判断方法很简单如果题目里出现了连通分区圈子冗余连接是否属于同一集合这些词优先往并查集想。另外分享一下我在用通义千问等代码辅助工具排查本地测试用例时的习惯先把自己的代码和测试数据喂进去请工具帮忙检查有没有数组越界或逻辑漏洞但核心算法一定自己先想清楚。工具可以帮你节省 debug 时间却不能替你做抽象建模。最后一个小建议不要只满足于 AC。拿出草稿纸把一个 4x5 的网格手动模拟一遍合并过程你才能真切感受到 count 是怎么一步步降下来的。写完并查集版本后再回头写一遍 DFS 版本比较两种思维差异。这样花的一个小时性价比比闷头刷十道新题高得多。
——类、作用域解析、统一初始化和指派初始化)
