200. 岛屿数量

200. 岛屿数量

1. 题目

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

2. 思路

a. 深度搜索

• 已知题目要求计算出二维数组中岛屿的数量，岛屿即是被水包围着的独立空间，依据题目意思，水的值为0，陆地的值为1
• 可以采用深度搜索的方法，来计算出岛屿的数量，初始化helper方法用于遍历每一个二维数组位置，进行深度搜索
• 当helper方法返回true时，则表示该单元格未被访问过 且 可以单独形成岛屿
• 当helper方法返回false时，则表示该单元格无法形成岛屿，无法形成岛屿的原因有两种：
  • 该单元格为水面
  • 该单元格已统计进其他岛屿的面积，因此本次不再计算
• helper方法内，如果本次遍历的单元格不为陆地，则直接返回false
• 否则则代表该单元格为陆地，下一步则是将该单元格标记为已统计，并进行深度遍历
• 深度遍历则是按照4个方向：上下左右，进行岛屿的同化操作，指的是将可以同化为岛屿面积内的单元格值变更为-，以便后续遍历时，不会将其统计为新的岛屿
• 过程中涉及到方向的移动，需要利用二维数组{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}与当前坐标进行相加，得到上下左右移动的效果
• 在得到新的坐标时，需要实时计算出新下标的有效性

b. 并查集

并查集（Disjoint Set Union，简称并查集）是一种用于处理集合的数据结构，通常用于解决等价关系的问题。它支持两个主要操作：查找（Find）和合并（Union）

在并查集中，每个元素被赋予一个唯一的标识符，通常是一个整数。这些元素被组织成若干集合，每个集合中的元素被认为是等价的

并查集主要有两个基本操作：

1. 查找（Find）： 查找操作用于确定一个元素所属的集合（也称为根结点或代表元素）。这通常涉及沿着指向父节点的指针链一直向上查找，直到找到根节点
2. 合并（Union）： 合并操作用于将两个集合合并为一个。这涉及找到两个元素所在集合的根节点，然后将其中一个根节点的父节点指向另一个根节点，从而将两个集合合并

并查集的一个常见应用是解决连通性问题，例如在图论中的最小生成树算法（如Kruskal算法）和计算图中的连通分量等。并查集的时间复杂度通常很小，使其成为一种高效的数据结构用于处理等价关系

• 当前场景中，要求的是二维数组中被水包围着的独立空间数量，即岛屿数量，而通过并查集可以将相连的陆地通过合并的方式进行聚簇
• 根据以上可以得知最重要的操作则是并查集的查找和合并，初始化并查集UnionFind类，通过传入的size来初始化parent一位数组，并将其各个单元格的parent初始化为本身，并初始化size 变量作为当前的根节点数量（如果两个节点进行合并，则根节点数量-1）
• 将二维数组的总个数平铺传入UnionFind类作为初始化个数
• 遍历二维数组grid，如果遇到grid单元格为1，则以此为发散点，将其四个方向（上下左右）为陆地的节点都进行union操作
• 如果遍历的过程中grid单元格不为1，则说明是水面，此时将水面计数waterCount + 1
• 完成遍历后，使用unionFind.size - waterCount得到岛屿数量

3. 代码

a. 深度搜索

class Solution {
    private static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    private int totalRow;
    private int totalCol;

    public int numIslands(char[][] grid) {
        totalRow = grid.length;
        totalCol = grid[0].length;
        var count = 0;

        for (var i = 0; i < totalRow; ++i) {
            for (var j = 0; j < totalCol; ++j) {
                if (helper(grid, i, j)) {
                    count++;
                }
            }
        }

        return count;
    }

    private boolean helper(char[][] grid, int row, int col) {
        if(grid[row][col] != '1') {
            return false;
        }

        grid[row][col] = '-';

        for (var i = 0; i < 4; ++i) {
            var direction = DIRECTIONS[i];
            var x = row + direction[0];
            var y = col + direction[1];

            if (isValidIndex(x, y)) {
                helper(grid, x, y);
            }
        }

        return true;
    }

    private boolean isValidIndex(int row, int col) {
        return row >= 0 && row < totalRow && col >= 0 && col < totalCol;
    }

}

b. 并查集

class Solution {
    private static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    private int totalRow;
    private int totalCol;

    class UnionFind {
        private int size;
        private int[] parent;

        public UnionFind(int size) {
            this.parent = new int[size];

            for (var i = 0; i < size; ++i) {
                parent[i] = i;
            }

            this.size = size;
        }

        public int find(int a) {
            return parent[a] != a ? parent[a] = find(parent[a]) : parent[a];
        }

        public void union(int a, int b) {
            var aParent = find(a);
            var bParent = find(b);

            if (aParent != bParent) {
                parent[aParent] = bParent;
                --size;
            }
        }
    }

    public int numIslands(char[][] grid) {
        totalRow = grid.length;
        totalCol = grid[0].length;
        var unionFind = new UnionFind(totalRow * totalCol);
        var waterCount = 0;

        for (var row = 0; row < totalRow; ++row) {
            for (var col = 0; col < totalCol; ++col) {
                if (grid[row][col] == '1') {
                    for (var i = 0; i < 4; ++i) {
                        var direction = DIRECTIONS[i];
                        var x = row + direction[0];
                        var y = col + direction[1];

                        if (isValidIndex(x, y) && grid[x][y] == '1') {
                            unionFind.union(row * totalCol + col, x * totalCol + y);
                        } 
                    }
                } else {
                    waterCount++;
                }
            }
        }

        return unionFind.size - waterCount;
    }

    private boolean isValidIndex(int row, int col) {
        return row >= 0 && row < totalRow && col >= 0 && col < totalCol;
    }

}

4. 复杂度

a. 深度搜索

• 时间复杂度：O(M * N) ，虽然有两层循环嵌套，但是每个单元格至多会被遍历一次
• 空间复杂度：O(1)

b. 并查集

• 时间复杂度：未知
• 空间复杂度：O(M * N)