企业官网建设流程全解析

LeetCode 岛屿数量II题解

题目描述

给定一个 m x n 的二维网格，最初所有位置都是水。现在给定一个数组 positions，表示添加陆地的位置。返回每次添加陆地后岛屿的数量。

示例：

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

解题思路

方法：并查集

思路：

• 使用并查集来解决这个问题。
• 初始化一个二维数组记录每个位置是否已经是陆地。
• 对于每个添加的陆地，检查其四个邻居，如果是陆地则合并。
• 每次添加后岛屿数量加一，减去合并次数。

复杂度分析：

• 时间复杂度：O(k * α(m * n))，其中 k 是添加陆地的次数。
• 空间复杂度：O(m * n)。

代码实现

class UnionFind: def __init__(self, n): self.parent = list(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): px, py = self.find(x), self.find(y) if px == py: return False if self.rank[px] < self.rank[py]: px, py = py, px self.parent[py] = px if self.rank[px] == self.rank[py]: self.rank[px] += 1 self.count -= 1 return True def num_islands2(m, n, positions): uf = UnionFind(m * n) grid = [[False] * n for _ in range(m)] result = [] for pos in positions: i, j = pos[0], pos[1] index = i * n + j if not grid[i][j]: grid[i][j] = True uf.count += 1 if i > 0 and grid[i-1][j]: uf.union(index, (i-1) * n + j) if i < m - 1 and grid[i+1][j]: uf.union(index, (i+1) * n + j) if j > 0 and grid[i][j-1]: uf.union(index, i * n + j - 1) if j < n - 1 and grid[i][j+1]: uf.union(index, i * n + j + 1) result.append(uf.count) return result # 测试 def test_num_islands2(): m, n = 3, 3 positions = [[0,0], [0,1], [1,2], [2,1]] print(num_islands2(m, n, positions)) # 输出：[1, 1, 2, 2] if __name__ == "__main__": test_num_islands2()

总结

岛屿数量II是并查集的典型应用，每次添加陆地后更新岛屿数量。