LeetCode - 200 岛屿数量

偏执的太偏执、 2023-09-23 13:06 127阅读 0赞

### 题目来源 ###

[200. 岛屿数量 - 力扣（LeetCode）][200. _ - _LeetCode]

### 题目描述 ###

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

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

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

### 示例 ###

### 提示 ###

### 题目分析 ###

本题也是一道连通图问题，可以考虑使用并查集求解。

和[华为机试 - 发广播\_伏城之外的博客-CSDN博客][- _-CSDN]

以及[LeetCode - 547 省份数量\_伏城之外的博客-CSDN博客][LeetCode - 547 _-CSDN]

的区别在于，前面两道题都是直接给出了点与点之间的连接关系，而本题并没有给出，需要我们自己求解。

因此本题的难度要大于前面两题。

我们需要先求解grid中陆地（即1）与陆地的连接关系，然后才能执行并查集的合并逻辑。

首先，我们需要创建一个并查集结构，即一个一维数组fa，fa有n\*m个元素，其中n,m分别对应grid矩阵的行数和列数。

初始化时，fa\[k\] = i\*m + j，k取值范围是\[0, n\*m-1\]，fa和grid的对应关系如下

![1a0d28e19d2b43bb9030e29cbc1f597f.png][]

这样的话，我们就将一个二维关系，转为了一维关系。

然后，就可以分析grid中陆地与陆地之间的连接关系了：

首先需要判断grid\[i\]\[j\]是否1，即是否为陆地，若是，则继续下面逻辑：

陆地的连接关系，有四个方向，即上下左右，我们需要对每一个陆地的上下左右进行连接分析：

假设grid\[i\]\[j\]是陆地，分别判断

其上边，grid\[i-1\]\[j\]，是否为陆地，若为陆地，则fa数组的第 i\*m+j 个 和 第 (i-1)\*m+j 是连接的，我们将它们合并。

其下边，grid\[i+1\]\[j\]，判断同上

其左边，grid\[i\]\[j-1\]，判断同上

其右边，grid\[i\]\[j+1\]，判断同上

在分析完所有陆地的连接关系后，我们就可以定义并查集的合并和查找功能了具体实现和以前相同，不知道的小伙伴可以去看前面

[华为机试 - 发广播\_伏城之外的博客-CSDN博客][- _-CSDN]

中关于并查集的合并以及查找功能实现的原理。

最后，就是求解grid中有几块独立的陆地？

这里需要注意的是，初始化并查集时，我们假设grid元素全部都是陆地，且每个陆地都互不相连（PS：这里大家要以并查集结构的思维来看，fa数组中每个数组元素都指向自己，因此所有陆地偶都互不相连），此时共有count = n\*m个独立陆地。

当并查集将两块路径进行合并后，即count--。

但是并查集合并完后，最终count中还包含水区域，因此count还需要减去水区域的个数，这样count的数目才是独立陆地的数目。

### 算法源码 ###

/**
     * @param {character[][]} grid
     * @return {number}
     */
    var numIslands = function (grid) {
      let n = grid.length;
      let m = grid[0].length;
    
      const ufs = new UnionFindSet(n, m);
    
      for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
          if (grid[i][j] === "1") {
            if (j - 1 >= 0 && grid[i][j - 1] === "1") {
              ufs.union(i * m + j - 1, i * m + j);
            }
    
            if (i - 1 >= 0 && grid[i - 1][j] === "1") {
              ufs.union((i - 1) * m + j, i * m + j);
            }
    
            if (j + 1 < m && grid[i][j + 1] === "1") {
              ufs.union(i * m + j, i * m + j + 1);
            }
    
            if (i + 1 < n && grid[(i + 1, j)] === "1") {
              ufs.union(i * m + j, (i + 1) * m + j);
            }
          } else {
            ufs.count--;
          }
        }
      }
    
      return ufs.count;
    };
    
    class UnionFindSet {
      constructor(n, m) {
        this.fa = [];
        this.init(n, m);
        this.count = n * m;
      }
    
      init(n, m) {
        for (let i = 0; i < n * m; i++) {
          this.fa[i] = i;
        }
      }
    
      find(x) {
        if (x !== this.fa[x]) {
          this.fa[x] = this.find(this.fa[x]);
          return this.fa[x];
        }
        return x;
      }
    
      union(x, y) {
        let x_fa = this.find(x);
        let y_fa = this.find(y);
        if (x_fa !== y_fa) {
          this.fa[y_fa] = x_fa;
          this.count--;
        }
      }
    }

![da1177621a4740a3929e5eacefd56944.png][]

[200. _ - _LeetCode]: https://leetcode.cn/problems/number-of-islands/
[- _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127588130?spm=1001.2014.3001.5501
[LeetCode - 547 _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127605092?spm=1001.2014.3001.5501
[1a0d28e19d2b43bb9030e29cbc1f597f.png]: https://img-blog.csdnimg.cn/1a0d28e19d2b43bb9030e29cbc1f597f.png
[da1177621a4740a3929e5eacefd56944.png]: https://img-blog.csdnimg.cn/da1177621a4740a3929e5eacefd56944.png