题目

题目来源：力扣（LeetCode）

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

思路分析

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

  1. /**
  2.  * @param {character[][]} grid
  3.  * @return {number}
  4.  */
  5. // count 在全局定义，且不能在全局中父默认值，否则会导致某些测试用例通不过，这是LeetCode的以雷区
  6. let count; // 存储岛屿的数量
  7. var numIslands = function (grid) {
  8.   // 二维数组中数组的长度
  9.   let m = grid.length;
  10.   // 二维数组中内部数组的长度
  11.   let n = grid[0].length;
  12.   // 实例化并查集
  13.   let uf = new UnionFind(m * n);
  14.   count = 0;
  15.   // 对二维数组进行遍历，如果 grid[i][j] == '1' 时，count++
  16.   for (let i = 0; i < m; i++) {
  17.     for (let j = 0; j < n; j++) {
  18.       if (grid[i][j] == '1') {
  19.         count++;
  20.       }
  21.     }
  22.   }
  23.   // 找当前节点的上下左右节点是否为1，如果都为 1 ，则进行合并
  24.   for (let i = 0; i < m; i++) {
  25.     for (let j = 0; j < n; j++) {
  26.       if (grid[i][j] == '1') {//当前岛屿数量加1
  27.         if (i - 1 >= 0 && grid[(i - 1)][j] == '1') {// 当前节点的上边一个节点
  28.           uf.unite(i * n + j, (i - 1) * n + j);
  29.         }
  30.         if (i + 1 < m && grid[i + 1] [j] == '1') {// 当前节点的下边一个节点
  31.           uf.unite(i * n + j, (i + 1) * n + j);
  32.         }
  33.         if (j - 1 >= 0 && grid[i][j - 1] == '1') {// 当前节点的左边一个节点
  34.           uf.unite(i * n + j, i * n + j - 1);
  35.         }//
  36.         if (j + 1 < n && grid[i] [j + 1] == '1') {// 当前节点的右边一个节点
  37.           uf.unite(i * n + j, i * n + j + 1);
  38.         }
  39.       }
  40.     }
  42.   }
  43.   return count;
  44. };
  46.  class UnionFind {
  47.   constructor(n) {
  48.     // 元素所指向的父节点，parent[i] 表示第 i 个元素所指向的父节点
  49.     // 初始化时, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
  50.     this.parent = new Array(n).fill(0).map((value, index) => index);
  51.     // 树的层数，rank[i] 表示以 i 为根的集合所表示的树的层数
  52.     this.rank = new Array(n).fill(1);
  53.     // 节点的个数
  54.     this.setCount = n;
  55.   }
  57.   // 查找过程，查找元素 index 所在集合的编号(查找树的根节点)
  58.   findSet(index) {
  59.     // 不断去查询自己的父节点，直至根节点
  60.     // 根节点的标志是父节点就是本身  parent[index] == index
  61.     if (this.parent[index] != index) {
  62.       // 递归获取节点的父节点
  63.       this.parent[index] = this.findSet(this.parent[index]);
  64.     }
  65.     // 返回根节点
  66.     return this.parent[index];
  67.   }
  69.   // 合并两个集合
  70.   unite(index1, index2) {
  71.     let root1 = this.findSet(index1);
  72.     let root2 = this.findSet(index2);
  73.     // 根节点不一样，是两个不同的集合(两棵不同的树)
  74.     if (root1 != root2) {
  75.       // 根据树的层数合并集合
  76.       // 
  77.       if (this.rank[root1] < this.rank[root2]) {
  78.         // 这个判断如果 root2 所在树的层数 大于 root1，就交换两个父节点，这样始终让 root1 为父节点
  79.         [root1, root2] = [root2, root1];
  80.       }
  81.       // 将层数多的集合合并到集合少的集合
  82.       this.parent[root2] = root1;
  83.       this.rank[root1] += this.rank[root2];
  84.       this.setCount--;
  85.        count--
  86.     }
  87.   }
  89.   getCount() {
  90.     return this.setCount;
  91.   }
  93.   connected(index1, index2) {
  94.     return this.findSet(index1) === this.findSet(index2);
  95.   }
  96. }