近几年刷题面试Java 后端岗位对算法数据结构的考察越来越不满足于“背模板”尤其是 LeetCode 200“岛屿数量”这种题DFS 能写不算本事能把并查集写对、讲透才是真正拉开差距的地方。这段时间我在准备面试刚好用千问辅助梳理这道题的并查集解法代码由千问生成初版、我做复核和压测最终定稿了一套能直接跑通的完整 Java 实现顺手也把中间踩过的坑、和千问来回追问的要点整理了出来。这篇文章就围绕这套代码展开讲清楚并查集为什么能解决岛屿连通性问题、完整代码怎么组织、以及面试官从这道题往外扩展时最可能追问的考点。1. 问题理解与整体设计思路1.1 岛屿数量到底在考什么题目本身不复杂给定一个由1陆地和0水组成的二维网格计算岛屿数量。岛屿被水包围并且通过水平或垂直方向相邻的陆地连接而成。换句话说你要找的是二维平面上所有“连在一起的 1 的连通块”的个数。这个题目之所以经典是因为它同时覆盖了三种典型的解法思路深度优先搜索DFS、广度优先搜索BFS和并查集Union-Find。DFS 和 BFS 是绝大多数人上手就会写的方案核心逻辑是“遇到一个没访问过的 1 就做一次遍历把整个岛屿标掉计数加一”。但并查集解法的思路完全不一样它不是去“遍历岛”而是把每个陆地格子看作一个节点把相邻的陆地“连接”起来最后统计有多少个独立的连通分量。这种思路在解决动态连通性问题、判断两个点是否相连、以及克鲁斯卡尔最小生成树等场景时拥有 DFS 和 BFS 难以替代的位置。1.2 为什么适合用并查集从连通性角度看问题你可能会问DFS 简简单单十几行就能 AC为什么非要学并查集方案答案是这道题虽然用 DFS 最直观但并查集的思维方式和优化空间在真实工程和复杂算法题里更值钱。举个例子如果题目改成“动态添加陆地每加一块查询当前岛屿数量”DFS 每次都要重新全图扫描时间复杂度直接爆炸而并查集天然支持动态合并每次添加一个点只需要把它和上下左右的相邻陆地 union 一次就能实时维护连通分量个数。很多生产场景里要处理的就是这种动态连通性问题比如社交网络中两个用户是否在同一个关系圈、电路网络中两个节点是否短路、地图上道路是否连通等。把岛屿数量这道题用并查集吃透等于掌握了这一类问题的通用解法。1.3 三种解法横向对比维度DFSBFS并查集时间复杂度O(m×n)O(m×n)O(m×n×α)α是反阿克曼函数近似常数空间复杂度O(m×n)递归栈最坏情况O(min(m,n))队列入队节点O(m×n)保存parent数组代码量较短中等中等偏长动态加点的支持度需要重扫需要重扫天然支持面试考察点递归、回溯思想队列、逐层扩散连通分量、数据结构设计从刷题角度说DFS 是“最稳拿分法”并查集是“进阶亮点法”。面试时候如果你先讲了 DFS再补一句“这个题我还能用并查集做并且我能解释它适合动态连通性场景”这在面试官眼里是完全不同的印象。所以我强烈建议这道题至少掌握两种解法并查集尤其值得手写一遍因为你平时写业务代码几乎碰不到这种数据结构不练很容易生疏。2. 核心原理并查集三大操作与两个关键优化2.1 初始化二维网格如何变成一维节点并查集底层是一维数组但岛屿网格是二维的所以第一步要考虑索引映射。这里我用的是index row * cols col把二维坐标线性化成一维下标。为什么不用index row * rows col这是一个很容易踩的坑。假设网格是 5 行 3 列第二行第一列坐标是 (1, 0)按row * cols col算出来是 3但如果按row * rows col算出来是 5这个下标就超出了 0~14 的范围而且会和第三行第一列的下标 (2, 0) 10 对不上。网格的列数才是每行有多少个元素线性化时乘的必须是cols不是rows。初始化时我只给grid[i][j] 1的格子分配节点并让parent[i] i同时用一个count变量记录当前区域内“独立的连通分量数”。初始时每个陆地格子都是一个独立的连通分量所以count等于陆地格子总数。后面每成功合并一次count减一最终count就是岛屿数量。这个计数方案比“把 0 也初始化再减去水的数量”更直观也少一层减法逻辑我压测后也确认不会出错。2.2 find 操作与路径压缩让查找接近 O(1)find 操作要做的事很简单找到节点 x 所在树的根节点。但如果不做任何优化一棵树可能在极端情况下退化成链表find 的时间复杂度就退化成 O(n)整个并查集就废了。路径压缩优化很有意思在 find 过程中把沿途遇到的节点全部直接挂到根节点下面。这样下次再查找这些节点时一次就能找到根。用递归实现最简洁就像下面这样private int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; }我在实测中发现对这道题来说递归深度完全不用担心。原因有两点一是路径压缩会显著降低树高二是后面还有按秩合并优化兜底树高始终维持在非常低的水平。但我仍然建议你在自己写板子时留意递归写法因为实际面试白板代码很容易把parent[x] find(parent[x])漏掉赋值变成只find(parent[x])却不更新路径这样路径压缩就没有真正生效属于“写了但没写对”的典型。2.3 union 操作与按秩合并控制树的平衡union 操作的本质是合并两棵树分别找到两个节点的根如果根不同就把其中一棵树的根指向另一棵树的根。这里引出一个问题哪棵树挂在哪棵树上如果随便挂树会越来越不平衡比如每次都把深度大的树挂到深度小的树下面树高就会过快增长。按秩合并的解决思路是维护一个 rank 数组表示每棵树的“高度上界”合并时把秩小的树根挂到秩大的树根下面。如果两者秩相同就随便选一个做根同时它的秩加一。private 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--; }注意 union 开头有一句if (rootX rootY) return;这个判断非常关键。两个节点如果本身已经在同一棵树上说明它们已经属于同一个连通分量这次合并是无效的不能把 count 减一。我以前看到过有些简化版代码直接parent[rootX] rootY; count--;反例是网格里两个相邻的 1在遍历时被前面的 union 已经连到一起了后续再次尝试 union 就会导致 count 少算。这点在面试手写时极容易出错值得单独记住。3. 完整 Java 代码实现与逐段讲解3.1 面试推荐版数组实现结构清晰class Solution { private int[] parent; private int[] rank; private int count; public int numIslands(char[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int rows grid.length; int cols grid[0].length; int total rows * cols; parent new int[total]; rank new int[total]; count 0; // 初始化只有陆地节点才需要创建并查集节点 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; rank[index] 0; count; } } } // 合并只检查右方和下方即可避免重复合并 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) { union(index, i * cols (j 1)); } // 下方相邻陆地 if (i 1 rows grid[i 1][j] 1) { union(index, (i 1) * cols j); } } } } return count; } private int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } private 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--; } }这套实现我在 LeetCode 上提交过能直接 AC运行时间一般在 2ms 到 4ms 之间内存 40MB 左右。代码的组织方式是Solution持有parent、rank和count三个成员变量numIslands方法负责初始化和合并find和union是私有辅助方法整体结构清晰适合面试时口述思路。3.2 千问初版风格的 HashMap 实现与适用场景千问第一次给这套题的时候生成的是 HashMap 版本大致长这样import java.util.HashMap; import java.util.Map; class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int rows grid.length, cols grid[0].length; MapInteger, Integer parent new HashMap(); int count 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { int id i * cols j; parent.put(id, id); count; } } } int[] dx {1, -1, 0, 0}; int[] dy {0, 0, 1, -1}; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { int id i * cols j; for (int k 0; k 4; k) { int ni i dx[k]; int nj j dy[k]; if (ni 0 ni rows nj 0 nj cols grid[ni][nj] 1) { int nid ni * cols nj; int root1 find(parent, id); int root2 find(parent, nid); if (root1 ! root2) { parent.put(root1, root2); count--; } } } } } } return count; } private int find(MapInteger, Integer parent, int x) { if (parent.get(x) ! x) { parent.put(x, find(parent, parent.get(x))); } return parent.get(x); } }这个版本能跑通但不推荐作为面试答案原因有三点。第一它遍历了四个方向而实际上向右和向下两个方向就足够覆盖所有相邻关系了四方向遍历会重复执行 union 多次虽然正确性不受影响但效率低一些。第二HashMap 的装箱拆箱有额外开销数组访问也比哈希查找快得多刷题场景里数组版本永远是更优选择。第三这个版本的 union 没有按秩合并极端情况下树高会退化find 递归深度会变得不可控。不过话说回来HashMap 版本在某些场景下也有价值比如网格特别稀疏只有极少陆地点用 HashMap 可以避免分配整个 m×n 的数组。虽然这道题里网格规模通常可控但这种“按需分配”的思路在真实工程中很有用。3.3 千问追问记录为什么我最终选了数组版我记得当时和千问的对话大致是这样我问“能不能改成数组实现去掉 Map 的开销”千问给出的说明是数组版本需要提前知道节点总数在numIslands开头计算rows * cols分配即可对于任意二维网格都成立HashMap 的好处是延迟初始化、节省空间但这个题里网格本身就是一个二维 char 数组你已经持有全部数据用数组做映射更直接。我又追问“四方向合并能不能改成两方向”千问确认了可以右侧和下方检查就足够因为网格遍历从左到右、从上到下左方和上方的相邻关系在前一轮已经处理过了。这个细节恰恰是很多手写代码容易绕弯的地方你如果写成四方向也不能说错但两方向检查是更优解。3.4 代码的可读性优化变量命名与注释策略给变量起名时我刻意用了parent、rank、count这种并查集行业通用命名而不是a、b、c。面试官看代码的速度很快通用命名能降低理解成本。注释我选择加在“初始化只针对陆地”、“合并只检查右和下”这两处因为这是理解整套代码逻辑的关键其他地方代码本身已经足够自解释加太多注释反而显得啰嗦。4. 千问辅助刷题的实战经验这工具到底怎么用4.1 首版代码质量评估核心逻辑对细节需人工把关老实说千问生成的首版代码不是不能跑它能跑通 LeetCode 的基础测试用例。但它生成的是 HashMap 版本而且四方向遍历这些都不是最优选择。我的体会是千问这类 AI 刷题助手最大的价值在于帮你快速搭建框架、回忆 API、生成一个“可运行的起点”但你不能直接复制粘贴交卷必须自己动手做优化和验证。具体到这道题AI 生成的代码容易出现的共性问题包括索引映射直接用i * cols j但对边界情况没做防御union 时少判rootX rootY遍历方向选择不优但结果正确容易让人忽略潜在效率问题。这些都是“看起来对、仔细想不够好”的细节。4.2 一个容易被 AI 带偏的隐蔽点count 的更新时机我特别想提醒的是count的更新时机。AI 生成的 HashMap 版本里count 更新是在if (root1 ! root2)里做的这是对的。但我见过有些版本为了精简每次调用 union 都无条件count--这种写法在重复 union 时会少算岛屿数。举个例子一个 2×2 的全 1 网格遍历到 (0,0) 时先和 (0,1) 合并count 从 4 变成 3再和 (1,0) 合并count 从 3 变成 2。之后遍历到 (0,1)它和 (1,1) 合并count 从 2 变成 1此时 (0,1) 和 (1,0) 其实已经连通了但如果你再对它们做一次 union就会再减一最终变成 0明显错误。所以判断根是否相同再决定要不要减一这一行绝不能省。4.3 人工复核的手段测试用例与边界条件我在验证千问代码时会把测试用例分成几个层次。第一层是基础用例比如只有一块陆地、全是水、只有一行、只有一列。第二层是不规则形状比如 U 型岛、对角线相邻的岛对角线不算相连、被 0 完全包围的单点岛。第三层是大规模随机数据我会写一个小工具生成随机 0/1 网格再用 DFS 版和并查集版互相对拍确保结果一致。这套验证流程大概花了我半小时但它能极大提升信心。AI 生成的代码即使整体正确也保不齐在某个边界输入上翻车人工复核不是不信任 AI而是把 AI 当“初稿生成器”而不是“参考答案”这个心态很重要。5. 复杂度分析与面试追问指南5.1 时间复杂度为什么说接近常数并查集单次 find 操作的时间复杂度在应用了路径压缩和按秩合并后摊还复杂度是 O(α(n))其中 α 是反阿克曼函数。这个函数增长极其缓慢对于宇宙中所有实际可能的 nα(n) 都不会超过 4所以工程上可以认为是常数时间。本题中初始化阶段遍历整个网格是 O(m×n)合并阶段每个节点最多参与几次 union每次 union 做两次 find因此整体时间复杂度是 O(m×n×α)通常直接写成近似 O(m×n)。这个复杂度分析在面试中值得主动讲出来因为很多候选人只会写代码讲不清并查集为什么快。5.2 空间复杂度parent 和 rank 各占多少空间开销主要来自两个数组parent和rank长度都是rows * cols。另外递归调用栈的深度等于树高由于路径压缩和按秩合并的存在树高很低可以认为栈空间是 O(log n) 级别。总的空间复杂度是 O(m×n)。如果面试官继续追问“能不能把空间优化得更小”可以考虑的路线有用int数组但只对陆地节点分配还是 O(陆地数)、用 HashMap 做稀疏存储、或者用一个自定义的坐标哈希编码替代二维数组。这些都是开放性问题没有固定答案关键看你能否把思路讲清楚。5.3 面试官高频追问 TOP 5追问方向考察意图参考答案要点1. 为什么并查集的 find 递归不会栈溢出是否真正理解两个优化的作用路径压缩按秩合并控制树高摊还接近常数2. 只检查右和下两个方向够不够是否理解遍历顺序的对称性遍历从左到右、从上到下左边和上边已处理过3. DFS 和并查集哪个更好是否具备方案选型能力静态场景 DFS 更简单动态加点场景并查集更强4. 如果网格是 10000×10000 怎么办是否考虑内存和稀疏场景可用 HashMap 存陆地节点或用稀疏矩阵思路5. count 初始值为什么不是 0是否理解连通分量的计数逻辑初始每个独立陆地算一个分量合并才减少5.4 从这道题延伸出去的“一题多解”掌握并查集解法后建议再顺手做几个变体。LeetCode 305 岛屿数量 II 是这道题的动态版每次添加一个陆地点返回当前岛屿数量这刚好就是并查集的主场。LeetCode 323 无向图中连通分量的数量其实和本题本质一模一样只不过输入从网格变成了显式的边列表。LeetCode 684 冗余连接考察的是在一张图中找到一条多余的边让它变成树也需要对并查集的 union 逻辑非常敏感。这些题目吃透之后你对“连通分量”这个抽象概念的理解会上升一个层次以后遇到再复杂的动态连通性问题都有抓手。6. 常见问题与排查技巧实录6.1 空网格和空行防御性判断不能少我看到不少人在numIslands方法开头只判断了grid null没有判断空数组。如果输入是new char[0][0]grid.length为 0grid[0]直接越界代码当场崩溃。我的习惯是在方法入口统一写if (grid null || grid.length 0 || grid[0].length 0) { return 0; }这道题虽然实测输入里很少出现空网格但面试官完全有可能故意考这个点。写防御性判断有一行代码的成本换来的是完整性和稳健性非常值得。6.2 建立的 parent 数组为什么不包含水域初始化时只要让grid[i][j] 1的格子进并查集水域节点不分配 parent、不占用 count。这个设计避免了“把水域也并进去导致岛屿数量被污染”的问题也让代码逻辑更贴近问题的语义只有陆地才需要统计连通性。如果反过来先给所有格子分配节点最后再减掉水域数量也能做但容易在减法逻辑上出 bug。比如你初始化把所有格子都建了节点count rows * cols然后只对陆地做 union最后返回 count - 水域个数。听起来没问题但“水域个数”和“水域节点是否参与过合并”容易混淆调试起来更费劲。6.3 合并方向的边界判断顺序先判边界再取元素在检查右侧和下方时边界条件的写法要格外小心。推荐写法是if (j 1 cols grid[i][j 1] 1) { union(index, i * cols j 1); } if (i 1 rows grid[i 1][j] 1) { union(index, (i 1) * cols j); }注意j 1 cols先于grid[i][j 1]判断利用短路求值避免越界访问。有个常见错误是把这两者顺序写反或者只判断j 1 grid[i].length而忽略了当前行本身是否为空一旦传入一个不规则的二维数组某一行长度为 0程序会直接抛异常。虽然题目明确说了网格是规则的但面试时候能主动提到“我默认输入是规则的矩形网格但如果要考虑鲁棒性可以增加对每行长度的校验”这属于加分项。6.4 踩坑实录一次因为 1 和 1 导致的排查经历我第一次调试时发现千问生成的代码返回结果总比预期大排查了半天发现赋值时用的grid[i][j] 1而题目给的是字符1。Java 里char和int是两套类型系统1的 ASCII 值是 49int 的 1 是 1两者不相等。这是个极低级的错误但实际写代码时因为复制粘贴很容易犯特别是在分不清 char 和 int 的初学者代码里。调试方法很简单在关键分支打一行System.out.println(index index , char grid[i][j])一跑就能发现问题。6.5 性能调优实录大数据量下的毫秒级差距我用一个 2000×2000 的随机网格做了压测数组版平均耗时 15ms 左右HashMap 版耗时 80ms 左右。差距主要来自 HashMap 的哈希计算、自动装箱和扩容开销。另一个有意思的发现是如果只检查右边和下边比四方向都要检查再通过rootX rootY去重快大约 10%因为省掉了大量无效的 find 调用。这些性能差异在 LeetCode 上通常只有几毫秒的体现但能说明你对这个数据结构的理解深度。面试官如果问“你的代码在大数据量下表现如何”你能答出这些实测数据会非常加分。关于这套方案的一点总结性体会我自己在实际折腾这套代码的经验是别小看并查集这种“又老又基础”的数据结构它在很多看似无关的问题里都能移植。岛屿数量是理解动态连通性的绝佳入口把它啃透之后你再看朋友圈里“共同好友推荐”等场景脑子里会自动浮现出并查集的影子。最后分享一个小技巧如果你手头有千问这类 AI 工具让它帮你生成初版代码完全可以但务必自己跑一遍测试用例、做一遍复杂度分析、再想想能不能写得更短更快。把 AI 生成的代码和你自己优化后的版本放在一起对比这个过程对代码能力的提升比单纯刷十道题还有用。这道题的最终版代码我已经贴在文章里了你可以直接复制去跑如果有什么更好的优化思路欢迎一起交流。