岛屿数量

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：深度优先搜索 (DFS)、广度优先搜索 (BFS)、并查集

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]
输出：1

示例 2：

输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]
输出：3

---

2. 解题思路拆解

这道题是 网格类搜索 的经典入门题。我们的目标是找到连通分量的个数。

方法一：深度优先搜索 (DFS) - 沉岛思想

我们可以遍历整个网格。如果一个位置是 '1'：

1. 计数器 + 1 (发现了一个新岛屿)。
2. 启动 DFS：
   • 将当前位置标记为 '0' (或者其他非 '1' 的值，表示已访问/已沉没)。
   • 递归访问其上下左右四个邻居。
   • 如果邻居也是 '1'，继续递归沉岛。
3. 这样，一次 DFS 调用就会把与当前 '1' 相连的所有陆地都变成水。
4. 继续遍历网格，直到结束。

方法二：广度优先搜索 (BFS)

思路与 DFS 类似，只是遍历方式改为 BFS (使用队列)。

1. 遍历网格，遇到 '1'，计数器 + 1。
2. 将该位置加入队列，并标记为 '0'。
3. 循环处理队列：
   • 取出队首元素。
   • 检查其四周邻居，如果是 '1'，加入队列并标记为 '0'。

方法三：并查集 (Union-Find)

1. 初始化并查集，将所有 '1' 的位置看作独立的集合。
2. 遍历网格：
   • 如果当前是 '1'，尝试将其与 右边 和 下边 的 '1' 合并 (Union)。
   • (只需要看右和下，因为左和上在之前的遍历中已经处理过了)。
3. 最终岛屿数量 = 初始 '1' 的总数 - 成功合并的次数。
   • 或者直接统计并查集中 parent 指向自己的节点个数 (且该节点要是陆地)。

通常面试中 DFS 写法最简洁，推荐掌握。

---

3. 代码实现 (DFS)

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    if (!grid || grid.length === 0) return 0;
    
    const rows = grid.length;
    const cols = grid[0].length;
    let count = 0;
    
    // 沉岛函数
    const sink = (r, c) => {
        // 边界检查：如果越界或者不是陆地，直接返回
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') {
            return;
        }
        
        // 标记为已访问 (变成水)
        grid[r][c] = '0';
        
        // 递归处理上下左右
        sink(r + 1, c);
        sink(r - 1, c);
        sink(r, c + 1);
        sink(r, c - 1);
    };
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                count++;
                sink(i, j); // 将与当前 '1' 相连的所有陆地沉没
            }
        }
    }
    
    return count;
};

代码执行演示

输入：

1 1 0
1 0 0
0 0 1

1. Loop (0,0): is '1'. count=1.
   • sink(0,0) -> set (0,0)='0'.
   • Recurse (1,0) -> '1' -> set (1,0)='0'.
   • Recurse (0,1) -> '1' -> set (0,1)='0'.
   • ... DFS finishes sinking the top-left block.
   • Grid becomes:

     0 0 0
     0 0 0
     0 0 1

2. Loop continues... skips all '0's.
3. Loop (2,2): is '1'. count=2.
   • sink(2,2) -> set (2,2)='0'.
   • DFS finishes.
4. End loop. Return 2.

---

4. 复杂度分析

维度	描述
时间复杂度	$O(M \times N)$。$M$ 是行数，$N$ 是列数。每个网格最多被访问两次（一次在主循环，一次在 DFS 中）。
空间复杂度	$O(M \times N)$。最坏情况下（整个网格都是陆地），递归栈深度可能达到 $M \times N$。