岛屿数量

给你一个由 '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

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {};

方法一：深度优先搜索

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

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

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

const numIslands = (grid) => {
  let count = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === "1") {
        count++;
        turnZero(i, j, grid);
      }
    }
  }
  return count;
};
function turnZero(i, j, grid) {
  if (
    i < 0 ||
    i >= grid.length ||
    j < 0 ||
    j >= grid[0].length ||
    grid[i][j] === "0"
  )
    return;
  grid[i][j] = "0";
  turnZero(i, j + 1, grid);
  turnZero(i, j - 1, grid);
  turnZero(i + 1, j, grid);
  turnZero(i - 1, j, grid);
}

复杂度分析

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

方法二：广度优先搜索

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

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

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

const numIslands = (grid) => {
  let count = 0;
  let queue = [];
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === "1") {
        count++;
        grid[i][j] = "0"; // 做标记，避免重复遍历
        queue.push([i, j]);
        turnZero(queue, grid);
      }
    }
  }
  return count;
};
function turnZero(queue, grid) {
  const dirs = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];
  while (queue.length) {
    const cur = queue.shift();
    for (const dir of dirs) {
      const x = cur[0] + dir[0];
      const y = cur[1] + dir[1];
      if (
        x < 0 ||
        x >= grid.length ||
        y < 0 ||
        y >= grid[0].length ||
        grid[x][y] !== "1"
      ) {
        continue;
      }
      grid[x][y] = "0";
      queue.push([x, y]);
    }
  }
}

复杂度分析

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

方法三：并查集

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

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

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

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  const Y = grid.length;
  const X = grid[0].length;
  const uf = new UnionFind();

  for (let i = 0; i < Y; i++) {
    for (let j = 0; j < X; j++) {
      if (grid[i][j] == 1) uf.makeSet([i, j]);
    }
  }

  for (let i = 0; i < Y; i++) {
    for (let j = 0; j < X; j++) {
      if (grid[i][j] == 1) {
        console.log(i, j);
        if (i + 1 < Y && grid[i + 1][j] == 1) uf.union([i, j], [i + 1, j]); // 右侧
        if (j + 1 < X && grid[i][j + 1] == 1) uf.union([i, j], [i, j + 1]); // 下侧
      }
    }
  }

  return uf.getCount();
};
class UnionFind {
  constructor() {
    this.parents = {};
    this.count = 0;
  }
  makeSet(x) {
    this.parents[x] = x + "";
    this.count++;
  }
  findSet(x) {
    // 路径压缩，查x的根节点
    while (this.parents[x] !== x + "") {
      x = this.parents[x];
    }
    return x + "";
  }
  union(x, y) {
    this.link(this.findSet(x), this.findSet(y));
  }
  link(x, y) {
    if (x === y) return;
    this.parents[x] = y;
    this.count--;
  }
  getCount() {
    return this.count;
  }
}

复杂度分析

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