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'] ]

输出：3

2.2 关键概念解析

理解这个问题需要明确几个关键点：

1. 网格表示：通常用二维数组表示，每个元素要么是'1'要么是'0'
2. 相邻定义：仅考虑上下左右四个方向，不考虑对角线
3. 岛屿定义：一组相邻的'1'组成一个岛屿

3. 解决方案设计

3.1 基本思路

解决这个问题的核心思路是遍历整个网格，当遇到一个'1'时，就找到了一个岛屿，然后需要把这个岛屿的所有相邻'1'都标记为已访问，避免重复计数。

3.2 算法选择

主要有两种经典算法可以解决这个问题：

1. 深度优先搜索(DFS)
2. 广度优先搜索(BFS)

两种方法的时间复杂度都是O(M×N)，其中M和N分别是网格的行数和列数。

4. 深度优先搜索实现

4.1 算法步骤

1. 遍历网格中的每个单元格
2. 当遇到'1'时，岛屿计数加1
3. 从这个'1'开始进行DFS，将所有相连的'1'标记为'0'(表示已访问)
4. 继续遍历直到网格结束

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(r+1, c) dfs(r-1, c) dfs(r, c+1) 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 count

4.3 复杂度分析

• 时间复杂度：O(M×N)，每个单元格最多被访问两次
• 空间复杂度：O(M×N)，最坏情况下递归栈的深度

5. 广度优先搜索实现

5.1 算法步骤

1. 遍历网格中的每个单元格
2. 当遇到'1'时，岛屿计数加1
3. 初始化一个队列，将当前'1'的位置加入队列
4. 从队列中取出位置，检查其四个邻居
5. 如果是'1'，则标记为'0'并加入队列
6. 重复直到队列为空

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 count

5.3 复杂度分析

• 时间复杂度：O(M×N)
• 空间复杂度：O(min(M,N))，队列的最大长度

6. 并查集解决方案

6.1 并查集简介

并查集(Disjoint Set Union)是一种数据结构，用于处理不相交集合的合并与查询问题。它支持两种操作：

1. Find：查找元素所属集合
2. Union：合并两个集合

6.2 算法思路

1. 初始化并查集，每个'1'的单元格都是一个独立集合
2. 遍历网格，对于每个'1'，检查其右侧和下侧的邻居
3. 如果邻居也是'1'，则合并这两个集合
4. 最后统计独立集合的数量

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[r+1][c] == '1': uf.union(index, (r+1)*cols + c) if c + 1 < cols and grid[r][c+1] == '1': uf.union(index, r*cols + c+1) return uf.count

6.4 复杂度分析

• 时间复杂度：O(M×N×α(M×N))，其中α是反阿克曼函数，增长极慢
• 空间复杂度：O(M×N)

7. 性能比较与选择

7.1 三种方法对比

7.2 选择建议

1. 面试场景：推荐DFS或BFS，代码简洁易懂
2. 大规模网格：BFS更优，避免递归栈溢出
3. 动态岛屿合并：并查集是唯一选择

8. 常见问题与优化

8.1 边界条件处理

• 空输入：直接返回0
• 单行或单列网格：需要特殊处理吗？不需要，通用解法适用
• 全'0'或全'1'的情况：需要正确处理

8.2 优化技巧

1. 原地修改：直接修改输入网格来标记访问状态
2. 提前终止：如果已经访问所有'1'，可以提前结束
3. 并行处理：对于极大网格，可以考虑并行算法

8.3 常见错误

1. 忘记标记已访问的单元格，导致无限循环
2. 错误处理网格边界，导致数组越界
3. 对角线相邻误认为属于同一岛屿

9. 实际应用场景

9.1 图像处理

在图像处理中，岛屿数量问题可以用于：

• 连通区域分析
• 目标检测
• 图像分割

9.2 地理信息系统

• 真实岛屿计数
• 湖泊识别
• 地块划分

9.3 社交网络

• 寻找独立用户群体
• 社区发现
• 网络连通性分析

10. 变种问题

10.1 最大岛屿面积

不仅计算岛屿数量，还要找出最大岛屿的面积

10.2 封闭岛屿数量

统计完全被水('0')包围的岛屿数量

10.3 不同形状岛屿

识别并统计不同形状的岛屿数量

11. 个人实现心得

在实际编码实现时，我有几点经验分享：

1. 优先考虑DFS实现，代码通常更简洁
2. 使用BFS时，注意队列的实现方式，Python中deque比list效率更高
3. 并查集的路径压缩优化能显著提升性能
4. 测试时要考虑极端情况，如全'1'、全'0'、单行、单列等
5. 在标记访问状态时，可以直接修改输入数组，避免额外空间开销