企业官网建设流程全解析

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()

总结

岛屿数量是并查集的典型应用，将相邻的陆地合并，最后统计集合数量。