.jpg)
1003 字
5 分钟
岛屿数量
题目描述
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
解题思路
- 深度优先搜索（DFS）：
- 遍历网格，遇到陆地(‘1’)启动DFS
- 将相连陆地标记为已访问
- 标记策略：
- 直接修改原网格：陆地→水域(‘0’)
- 或使用独立访问矩阵（空间换安全）
- 四连通方向：
- 递归探索上下左右相邻单元格
- 边界检查防止越界
- 岛屿计数：
- 每次DFS启动计数加一
- 遍历顺序：
- 按行扫描确保覆盖全部区域
- 已标记区域自动跳过
关键洞察
- 连通域本质：
- 岛屿定义为四连通（非八连通）的陆地组
- 对角线分离不算同一岛屿
- 标记即删除：
- 通过标记避免重复计数
- 隐式实现岛屿分离
- 无回溯需求：
- 仅需标记无需恢复状态
- 简化DFS实现逻辑
- 遍历完整性：
- 顺序扫描保证所有岛屿被发现
- 跳过水域和已访问区域提升效率
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(M×N)：每个单元格访问一次 |
| 空间复杂度 | O(M×N)：DFS递归栈最大深度 |
| 或 O(1)（修改原网格时） |
代码实现
/** * @param {character[][]} grid * @return {number} */var numIslands = function (grid) {
const m = grid.length; const n = grid[0].length; let result = 0
const turnZero = (i, j) => { if (i < 0 || i >= m || j < 0 || j >= n) return; if (grid[i][j] === '0') return;
grid[i][j] = '0'
turnZero(i, j + 1); turnZero(i, j - 1); turnZero(i + 1, j); turnZero(i - 1, j); }
for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] === '1') { result++; turnZero(i, j) } } }
return result;};迭代版本
const numIslands = (grid) => { if (!grid.length) return 0;
const rows = grid.length; const cols = grid[0].length; let count = 0; const directions = [[-1,0], [1,0], [0,-1], [0,1]];
for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === '1') { count++; grid[r][c] = '0'; // 标记访问 const queue = [[r, c]];
while (queue.length) { const [curR, curC] = queue.shift(); for (const [dr, dc] of directions) { const newR = curR + dr; const newC = curC + dc; if (newR >= 0 && newR < rows && newC >=0 && newC < cols && grid[newR][newC]==='1') { queue.push([newR, newC]); grid[newR][newC] = '0'; // 提前标记避免重复入队 } } } } } } return count;};变种：统计岛屿面积
const maxAreaOfIsland = (grid) => { let maxArea = 0;
const dfs = (r, c) => { if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] !== 1) { return 0; }
grid[r][c] = 0; // 标记为已访问 let area = 1;
area += dfs(r + 1, c); area += dfs(r - 1, c); area += dfs(r, c + 1); area += dfs(r, c - 1);
return area; };
for (let r = 0; r < grid.length; r++) { for (let c = 0; c < grid[0].length; c++) { if (grid[r][c] === 1) { maxArea = Math.max(maxArea, dfs(r, c)); } } }
return maxArea;};并查集实现（适合动态变化场景）
class UnionFind { constructor(grid) { this.count = 0; this.parent = []; this.rank = [];
const rows = grid.length; const cols = grid[0].length;
for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === '1') { this.parent.push(r * cols + c); this.count++; } else { this.parent.push(-1); } this.rank.push(0); } } }
// 实现并查集标准方法...}实际应用场景
- 地图分析：卫星图像中识别陆地与岛屿`
- 游戏开发：生成随机岛屿地图`
- 网络分析：社交网络中独立社群数量统计`
- 医学影像：CT扫描中细胞团簇计数`