方法一：深度优先搜索

我们可以将二维网格看成一个无向图，竖直或水平相邻的 11 之间有边相连。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 00。

最终岛屿的数量就是我们进行深度优先搜索的次数。

复制
1const numIslands = (grid) => {
2  let count = 0
3  for (let i = 0; i < grid.length; i++) {
4    for (let j = 0; j < grid[0].length; j++) {
5      if (grid[i][j] === '1') {
6        count++
7        turnZero(i, j, grid)
8      }
9    }
10  }
11  return count
12}
13function turnZero(i, j, grid) {
14  if (i < 0 || i >= grid.length || j < 0 
15       || j >= grid[0].length || grid[i][j] === '0') return
16  grid[i][j] = '0'
17  turnZero(i, j + 1, grid)
18  turnZero(i, j - 1, grid)
19  turnZero(i + 1, j, grid)
20  turnZero(i - 1, j, grid)
21}

复杂度分析

• 时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
• 空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。

方法二：广度优先搜索

同样地，我们也可以使用广度优先搜索代替深度优先搜索。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 00。直到队列为空，搜索结束。

最终岛屿的数量就是我们进行广度优先搜索的次数。

复制
1const numIslands = (grid) => {
2  let count = 0
3  let queue = []
4  for (let i = 0; i < grid.length; i++) {
5    for (let j = 0; j < grid[0].length; j++) {
6      if (grid[i][j] === '1') {
7        count++
8        grid[i][j] = '0' // 做标记，避免重复遍历
9        queue.push([i, j])
10        turnZero(queue, grid)
11      }
12    }
13  }
14  return count
15}
16function turnZero(queue, grid) {
17  const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
18  while (queue.length) {
19    const cur = queue.shift()
20    for (const dir of dirs) {
21      const x = cur[0] + dir[0]
22      const y = cur[1] + dir[1]
23      if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] !== '1') {
24        continue
25      }
26      grid[x][y] = '0'
27      queue.push([x, y])
28    }
29  }
30}

复杂度分析

• 时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
• 空间复杂度：O(min(M,N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)。

方法三：并查集

同样地，我们也可以使用并查集代替搜索。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并。

最终岛屿的数量就是并查集中连通分量的数目。

复制
1/**
2 * @param {character[][]} grid
3 * @return {number}
4 */
5var numIslands = function(grid) {
6    const Y = grid.length;
7    const X = grid[0].length;
8    const uf = new UnionFind();
9
10    for(let i = 0; i < Y; i++) {
11        for(let j = 0; j < X; j++) {
12            if(grid[i][j] == 1) uf.makeSet([i, j]);
13        }
14    }
15
16    for(let i = 0; i < Y; i++) {
17        for(let j = 0; j < X; j++) {
18            if (grid[i][j] == 1) {
19                console.log(i , j)
20                if ((i + 1 < Y) && (grid[i + 1][j] == 1)) uf.union([i, j], [i + 1, j]); // 右侧
21                if ((j + 1 < X) && (grid[i][j + 1] == 1)) uf.union([i, j], [i, j + 1]); // 下侧
22            }
23        }
24    }
25
26    return uf.getCount();
27};
28class UnionFind {
29    constructor() {
30        this.parents = {};
31        this.count = 0;
32    }
33    makeSet(x) {
34        this.parents[x] = x + '';
35        this.count++;
36    }
37    findSet(x) { // 路径压缩，查x的根节点
38        while (this.parents[x] !== (x + '')) {
39            x = this.parents[x];
40        }
41        return x + '';
42    }
43    union(x, y) {
44        this.link(this.findSet(x), this.findSet(y));
45    }
46    link(x, y) {
47        if (x === y) return;
48        this.parents[x] = y;
49        this.count--;
50    }
51    getCount() {
52        return this.count;
53    }
54}

复杂度分析

• 时间复杂度：O(MN×α(MN))，其中 MM 和 NN 分别为行数和列数。注意当使用路径压缩（见 find 函数）和按秩合并（见数组 rank）实现并查集时，单次操作的时间复杂度为 α(MN)，其中 α(x) 为反阿克曼函数，当自变量 xx 的值在人类可观测的范围内（宇宙中粒子的数量）时，函数 α(x) 的值不会超过 5，因此也可以看成是常数时间复杂度。
• 空间复杂度：O(MN)，这是并查集需要使用的空间。