LeetCode 305. Number of Islands II 题解

LeetCode 305. Number of Islands II 题解题目描述给你一个 m x n 的网格其中 0 表示水1 表示陆地。初始时网格中全是 0 。现在你需要执行addLand操作每次操作会将一个位置 (r, c) 变为 1 。请你计算每次addLand操作后网格中岛屿的数量。示例 1输入m 3, n 3, positions [[0,0], [0,1], [1,2], [2,1]] 输出[1, 1, 2, 3] 解释 初始时网格是全 0 的。 操作 1addLand(0, 0) → 岛屿数为 1 操作 2addLand(0, 1) → 岛屿数为 1与之前的陆地相连 操作 3addLand(1, 2) → 岛屿数为 2不与之前的陆地相连 操作 4addLand(2, 1) → 岛屿数为 3不与之前的陆地相连解题思路使用并查集Union-Find数据结构来解决每次添加陆地时检查其四个邻居是否是陆地如果邻居是陆地进行合并操作岛屿数量 当前陆地数量 - 合并次数代码实现class UnionFind: def __init__(self, size): self.parent list(range(size)) 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: self.parent[root_y] root_x self.count - 1 def numIslands2(m, n, positions): uf UnionFind(m * n) grid [[0] * n for _ in range(m)] result [] directions [(0, 1), (1, 0), (0, -1), (-1, 0)] for r, c in positions: if grid[r][c] 1: result.append(uf.count) continue grid[r][c] 1 uf.count 1 for dr, dc in directions: nr, nc r dr, c dc if 0 nr m and 0 nc n and grid[nr][nc] 1: uf.union(r * n c, nr * n nc) result.append(uf.count) return result复杂度分析时间复杂度O(k α(mn))其中 k 是操作次数α 是阿克曼函数的反函数空间复杂度O(mn)测试案例# 测试案例 1 assert numIslands2(3, 3, [[0,0], [0,1], [1,2], [2,1]]) [1, 1, 2, 3] # 测试案例 2 assert numIslands2(1, 1, [[0,0]]) [1] # 测试案例 3 assert numIslands2(2, 2, [[0,0], [1,1], [0,1], [1,0]]) [1, 2, 1, 1]总结本题是并查集的经典应用。关键点并查集用于处理连通性问题每次添加陆地时检查邻居维护岛屿数量通过本题可以深入理解并查集的应用场景。