1. 岛屿数量问题解析今天我们来聊聊这个经典的算法问题——岛屿数量。第一次看到这个题目时你可能觉得它很简单但深入思考后会发现其中蕴含着不少值得探讨的细节。这个问题不仅常见于技术面试在实际应用中也有很多场景比如图像处理中的连通区域分析、地理信息系统中的岛屿识别等。2. 问题定义与理解2.1 问题描述给定一个由1(陆地)和0(水)组成的二维网格计算网格中岛屿的数量。岛屿被水包围并且通过水平或垂直方向上相邻的陆地连接形成。你可以假设网格的四个边都被水包围。示例输入[ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ]输出32.2 关键概念解析理解这个问题需要明确几个关键点网格表示通常用二维数组表示每个元素要么是1要么是0相邻定义仅考虑上下左右四个方向不考虑对角线岛屿定义一组相邻的1组成一个岛屿3. 解决方案设计3.1 基本思路解决这个问题的核心思路是遍历整个网格当遇到一个1时就找到了一个岛屿然后需要把这个岛屿的所有相邻1都标记为已访问避免重复计数。3.2 算法选择主要有两种经典算法可以解决这个问题深度优先搜索(DFS)广度优先搜索(BFS)两种方法的时间复杂度都是O(M×N)其中M和N分别是网格的行数和列数。4. 深度优先搜索实现4.1 算法步骤遍历网格中的每个单元格当遇到1时岛屿计数加1从这个1开始进行DFS将所有相连的1标记为0(表示已访问)继续遍历直到网格结束4.2 代码实现def numIslands(grid): if not grid: return 0 count 0 rows, cols len(grid), len(grid[0]) def dfs(r, c): if r 0 or c 0 or r rows or c cols or grid[r][c] ! 1: return grid[r][c] 0 # 标记为已访问 dfs(r1, c) dfs(r-1, c) dfs(r, c1) dfs(r, c-1) for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 dfs(r, c) return count4.3 复杂度分析时间复杂度O(M×N)每个单元格最多被访问两次空间复杂度O(M×N)最坏情况下递归栈的深度5. 广度优先搜索实现5.1 算法步骤遍历网格中的每个单元格当遇到1时岛屿计数加1初始化一个队列将当前1的位置加入队列从队列中取出位置检查其四个邻居如果是1则标记为0并加入队列重复直到队列为空5.2 代码实现from collections import deque def numIslands(grid): if not grid: return 0 count 0 rows, cols len(grid), len(grid[0]) for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 grid[r][c] 0 queue deque([(r, c)]) while queue: row, col queue.popleft() for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc row dr, col dc if 0 nr rows and 0 nc cols and grid[nr][nc] 1: grid[nr][nc] 0 queue.append((nr, nc)) return count5.3 复杂度分析时间复杂度O(M×N)空间复杂度O(min(M,N))队列的最大长度6. 并查集解决方案6.1 并查集简介并查集(Disjoint Set Union)是一种数据结构用于处理不相交集合的合并与查询问题。它支持两种操作Find查找元素所属集合Union合并两个集合6.2 算法思路初始化并查集每个1的单元格都是一个独立集合遍历网格对于每个1检查其右侧和下侧的邻居如果邻居也是1则合并这两个集合最后统计独立集合的数量6.3 代码实现class UnionFind: def __init__(self, grid): rows, cols len(grid), len(grid[0]) self.parent [i for i in range(rows * cols)] self.count sum(grid[r][c] 1 for r in range(rows) for c in range(cols)) def find(self, i): if self.parent[i] ! i: self.parent[i] self.find(self.parent[i]) return self.parent[i] def union(self, x, y): rootx self.find(x) rooty self.find(y) if rootx ! rooty: self.parent[rootx] rooty self.count - 1 def numIslands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind(grid) for r in range(rows): for c in range(cols): if grid[r][c] 1: index r * cols c if r 1 rows and grid[r1][c] 1: uf.union(index, (r1)*cols c) if c 1 cols and grid[r][c1] 1: uf.union(index, r*cols c1) return uf.count6.4 复杂度分析时间复杂度O(M×N×α(M×N))其中α是反阿克曼函数增长极慢空间复杂度O(M×N)7. 性能比较与选择7.1 三种方法对比方法时间复杂度空间复杂度适用场景DFSO(M×N)O(M×N)网格较小递归深度可控BFSO(M×N)O(min(M,N))网格较大避免递归栈溢出并查集O(M×N×α(M×N))O(M×N)需要动态处理岛屿合并7.2 选择建议面试场景推荐DFS或BFS代码简洁易懂大规模网格BFS更优避免递归栈溢出动态岛屿合并并查集是唯一选择8. 常见问题与优化8.1 边界条件处理空输入直接返回0单行或单列网格需要特殊处理吗不需要通用解法适用全0或全1的情况需要正确处理8.2 优化技巧原地修改直接修改输入网格来标记访问状态提前终止如果已经访问所有1可以提前结束并行处理对于极大网格可以考虑并行算法8.3 常见错误忘记标记已访问的单元格导致无限循环错误处理网格边界导致数组越界对角线相邻误认为属于同一岛屿9. 实际应用场景9.1 图像处理在图像处理中岛屿数量问题可以用于连通区域分析目标检测图像分割9.2 地理信息系统真实岛屿计数湖泊识别地块划分9.3 社交网络寻找独立用户群体社区发现网络连通性分析10. 变种问题10.1 最大岛屿面积不仅计算岛屿数量还要找出最大岛屿的面积10.2 封闭岛屿数量统计完全被水(0)包围的岛屿数量10.3 不同形状岛屿识别并统计不同形状的岛屿数量11. 个人实现心得在实际编码实现时我有几点经验分享优先考虑DFS实现代码通常更简洁使用BFS时注意队列的实现方式Python中deque比list效率更高并查集的路径压缩优化能显著提升性能测试时要考虑极端情况如全1、全0、单行、单列等在标记访问状态时可以直接修改输入数组避免额外空间开销