从小白开始刷算法并查集篇 leetcode.200-阿里云开发者社区

示例 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

题目来源：力扣（LeetCode）

并查集介绍：

并查集（Disjoint Set Union，简称并查集）是一种用于处理集合合并和查询连通性的数据结构。它提供了两个主要操作：合并（union）和查找（find）。并查集主要用于解决一些关于集合的合并和查询问题，比如判断无向图中的连通分量、求解最小生成树、判断图中是否存在环等。并查集的核心思想是维护一个由多个集合构成的集合族，每个集合代表一个独立的连通分量。初始时，每个元素自成一个集合，然后通过不断的合并操作，将具有连通关系的元素合并到同一个集合中。通过查找操作，可以确定两个元素是否属于同一个集合。并查集的实现通常使用一个数组来表示集合，其中每个元素的值表示其所属集合的根节点。通过将不同集合的根节点连接在一起，形成一个森林结构，从而快速合并集合和查找元素所属的集合。并查集的常用操作：

初始化：创建一个并查集，每个元素自成一个集合。
查找：查找元素所属的集合，即找到其根节点。
合并：将两个集合合并成一个集合，即将两个根节点连接起来。

并查集的时间复杂度：

初始化：O(n)
查找：O(log n)（路径压缩优化后，接近常数时间）
合并：O(log n)（按秩合并优化后，接近常数时间）

并查集是一种简单而高效的数据结构，适用于解决一些集合合并和查询连通性的问题。它在图论、网络连接、最小生成树等领域都有广泛的应用。

并查集思路

能否写出：不能写出。

时间：1个小时起步第一次写

思路：

首先判断输入的二维字符数组 grid 是否为空或长度为0，如果是，则返回0，表示没有岛屿。
获取二维字符数组的行数和列数，分别赋值给变量 row 和 col。
创建一个 UnionFind 对象 uf，并将二维字符数组 grid 传入构造函数中进行初始化。
遍历二维字符数组grid，对每个元素进行如下操作：

如果当前元素为水域（‘0’），则计数器 waters 加1，表示遇到了一个水域。
如果当前元素为岛屿（‘1’），则根据上、下、左、右四个方向，判断相邻位置是否也是岛屿，如果是，则将它们通过并查集的 union 操作合并到同一个集合中。

返回并查集 uf 的岛屿数量 uf.getCount() 减去计数器 waters，即为实际岛屿的数量。

并查集的实现部分包含以下内容：

UnionFind 类有两个成员变量：root 数组和 count 计数器。
在构造函数中，根据二维字符数组 grid 的行数和列数，初始化 root 数组，并将每个位置的索引作为初始的根节点。
find 方法用于查找指定位置元素的根节点，并通过路径压缩将其直接连接到根节点，以加快后续查找操作的速度。
union 方法用于将两个元素合并到同一个集合中。首先找到两个元素的根节点，如果它们不相等，则将其中一个根节点指向另一个根节点，并将计数器 count 减1，表示合并了一个集合。
getCount 方法用于获取当前并查集中的集合数量。

通过并查集的操作，将相邻的岛屿合并到同一个集合中，最后返回集合数量减去水域数量，即为实际岛屿的数量。

// 仅是我的思路代码，leetcode上大神更厉害
class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        int waters = 0;
        UnionFind uf = new UnionFind(row * col);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '0') {
                    waters++;
                } else {
                    //上下左右的位置坐标
                    int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
                    for (int[] dir : directions) {
                        //通过当前ij位置坐标 计算 四周位置坐标
                        int x = i + dir[0];
                        int y = j + dir[1];
                        //判断边界问题
                        //xy必须是正数
                        //xy必须不超过行列
                        //坐标是岛屿
                        if (x >= 0 && y >= 0 && x < row && y < col && grid[x][y] == '1') {
                            //上下左右四方 相邻 的位置 x y, 当前位置 i j
                            uf.union(x * col + y, i * col + j);
                        }
                    }
                }
            }
        }
        //count是土地和水的合并，减去水就剩陆地的个数
        return uf.getCount() - waters;
    }
}
class UnionFind {
    private int[] parent;
    private int count;
    public UnionFind(int size) {
        count = size;
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }
    // Find the root of X
    public int find(int x) {
        if (x == parent[x]) {
            return x;
        }
        //将当前节点的父节点直接设为根节点
        return parent[x] = find(parent[x]);
    }
    /**
     * Union two element into one root
     *
     * @param x 要被更改的祖先
     * @param y 祖先
     */
    public void union(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);
        if (parentX != parentY) {
            parent[parentX] = parentY;
            //两块土地合成一块
            count--;
        }
    }
    public int getCount() {
        return count;
    }
}

时间复杂度：O(MNα(MN))

M 和 N 分别是二维字符数组 grid 的行数和列数，α 是 Ackermann 函数的反函数，它可以看作是一个很小的常数。

空间复杂度：O(MN)

用于存储并查集的根节点数组和计数器。
其他思路

从小白开始刷算法 dfs篇 leetcode.200

从小白开始刷算法并查集篇 leetcode.200

序言

200. 岛屿数量

并查集介绍：

并查集思路

热门文章

最新文章

相关课程

相关电子书

相关实验场景

从小白开始刷算法 并查集篇 leetcode.200

序言

200. 岛屿数量

并查集介绍：

并查集思路

热门文章

最新文章

相关课程

相关电子书

相关实验场景

从小白开始刷算法并查集篇 leetcode.200