LeetCode 岛屿数量II题解

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[i1][j]: uf.union(index, (i1) * n j) if j 0 and grid[i][j-1]: uf.union(index, i * n j - 1) if j n - 1 and grid[i][j1]: 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是并查集的典型应用每次添加陆地后更新岛屿数量。