LeetCode 岛屿数量题解

LeetCode 岛屿数量题解题目描述给定一个二维网格地图 1陆地和 0水计算岛屿的数量。示例输入grid [ [1,1,1,1,0], [1,1,0,1,0], [1,1,0,0,0], [0,0,0,0,0] ]输出1解题思路方法并查集思路使用并查集来解决这个问题。遍历网格将所有陆地与其相邻的陆地进行合并。最后统计集合的数量即为岛屿的数量。复杂度分析时间复杂度O(m * n)。空间复杂度O(m * n)。代码实现class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n 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 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 def num_islands(grid): if not grid: return 0 m, n len(grid), len(grid[0]) uf UnionFind(m * n) for i in range(m): for j in range(n): if grid[i][j] 1: index i * n j if i 0 and grid[i-1][j] 1: uf.union(index, (i-1) * n j) if j 0 and grid[i][j-1] 1: uf.union(index, i * n j - 1) count 0 for i in range(m): for j in range(n): if grid[i][j] 1 and uf.find(i * n j) i * n j: count 1 return count # 测试 def test_num_islands(): grid [ [1, 1, 1, 1, 0], [1, 1, 0, 1, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0] ] print(num_islands(grid)) # 输出1 if __name__ __main__: test_num_islands()总结岛屿数量是并查集的典型应用将相邻的陆地合并最后统计集合数量。