高频面试题深度讲解：如何用并查集做岛屿动态统计？

摘要

你想象一下，在一个全是水的地图上，陆陆续续加入岛屿块，你需要实时统计现在有多少个岛屿。这种需求在地理信息系统（GIS）、游戏地图生成、网络连通性监控等场景都很常见。LeetCode 305 就是这个题，它要求我们在每次添加一块陆地后，报告岛屿的总数。

最直接的暴力做法是每次都全图扫描一遍，但那显然太慢。这篇文章用 Swift 并查集（Disjoint Set）来解决这个问题，实现增量更新 O(α(N)) 的性能：速度快，代码好读，适合工程实战。

描述

给定一个 m × n 的网格，初始全是水（0）。我们会依次收到一系列「添加陆地」操作，每次将某个水点改为陆地（1），希望在每次操作后实时返回当前岛屿的数量——岛屿被定义为上下左右相连的陆地区域。

例如：

输入：m=3, n=3, positions=[[0,0],[0,1],[1,2],[2,1]]
输出：[1,1,2,3]

过程是：

• 加入 (0,0)：岛屿数 = 1
• 加入 (0,1)：连接到 (0,0)，岛屿数仍为 1
• 加入 (1,2)：新的岛屿，岛屿数 = 2
• 加入 (2,1)：又是新的岛屿，岛屿数 = 3

题解答案（Swift 实现）

下面是用并查集实现的完整 Swift 代码：

import Foundation

class NumIslands2 {
    private let m: Int, n: Int
    private var parent: [Int]
    private var rank: [Int]
    private var grid: [[Bool]]
    private var count = 0

    init(_ m: Int, _ n: Int) {
        self.m = m
        self.n = n
        parent = Array(repeating: -1, count: m * n)
        rank = Array(repeating: 0, count: m * n)
        grid = Array(repeating: Array(repeating: false, count: n), count: m)
    }

    func addLand(_ row: Int, _ col: Int) -> Int {
        let idx = row * n + col
        if grid[row][col] { return count }

        grid[row][col] = true
        parent[idx] = idx
        count += 1

        for dir in [(0,1),(1,0),(0,-1),(-1,0)] {
            let x = row + dir.0, y = col + dir.1
            if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] {
                let nid = x * n + y
                union(idx, nid)
            }
        }
        return count
    }

    private func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    private func union(_ x: Int, _ y: Int) {
        let rx = find(x), ry = find(y)
        if rx == ry { return }
        if rank[rx] < rank[ry] {
            parent[rx] = ry
        } else if rank[rx] > rank[ry] {
            parent[ry] = rx
        } else {
            parent[ry] = rx
            rank[rx] += 1
        }
        count -= 1
    }
}

// 可运行 Demo
func numIslands2(_ m: Int, _ n: Int, _ positions: [[Int]]) -> [Int] {
    let solution = NumIslands2(m, n)
    var result = [Int]()
    for pos in positions {
        result.append(solution.addLand(pos[0], pos[1]))
    }
    return result
}

题解代码分析

并查集（Union-Find）怎么用在网格上

• 我们把二维坐标 (r, c) 映射到一维 idx = r * n + c。
• parent[idx] 表示它在并查集中的父节点，rank 用来控制合并优化。
• 每次添加一个陆地，就初始化它为自己的根，并增加岛屿计数 count。
• 遍历上下左右四个方向，如果有相邻陆地，就把两个集合合并(union)，如果合并成功，岛屿数减一。

为什么这样会高效？

每次操作只需要 O(1) 查找和合并，通过路径压缩 + 按秩合并，使得并查集操作接近 O(α(N))。相比每次遍历整个网格做 DFS 干净利落，尤其对大网格、大批量操作的情况，非常有优势。

示例测试及结果

let positions = [[0,0],[0,1],[1,2],[2,1]]
print(numIslands2(3, 3, positions))
// 输出 [1, 1, 2, 3]

// 再试一组包含重复添加的位置
print(numIslands2(4, 4, [[0,0],[0,1],[1,1],[1,0],[0,0],[3,3]]))
// 依次返回 [1,1,1,1,1,2]

测试中发现，重复添加不会改变岛屿数，这符合题意，也说明代码里做了状态判断与保护。

时间复杂度

• 一共添加 k 次陆地操作，每次处理包括 1 次 find/union 和最多 4 次邻居检查。
• 并查集的 find/union 平摊时间复杂度是 O(α(mn))，α 是逆 Ackermann 函数，非常非常慢增长。
• 总体复杂度：O(k * α(mn))

这对于实际数据（m, n ≤ 10⁴, k ≤ 10⁴）几乎可以看作接近 O(k)。

空间复杂度

• 用到的数组包括 parent, rank 和 grid，每个都占 m×n 的空间。
• 所以总空间复杂度为 O(mn)，适合不超大网格的场景。

总结

• 本题提供了一个可以实时统计岛屿数量的实战模型，非常适合游戏地图、地理信息处理、网络连通性分析等场景使用。
• Swift 实现的并查集结构简洁且性能靠前，用了路径压缩 + 按秩合并，很容易复用到其他图结构问题。
• 如果想进一步提升，可以考虑使用分治、并行、网格切片等方法扩展这个结构到更复杂的系统中。