[LeetCode] 问题系列 - Number of Isla

200: Number of Islands

题目链接：https://leetcode.com/problems/number-of-islands/
这道是medium，有三种方法：BFS, DFS, Union Find。前两种比较直接，现在着重讲一下Union Find。

Union Find算法又叫并查集算法（disjoint-set union），最常见到的用法是：检查查询两个节点的连接状态。对于它的概念和介绍可以看看这个视频：https://www.youtube.com/watch?v=YKE4Vd1ysPI

305: Number of Islands II

题目链接：https://leetcode.com/problems/number-of-islands-ii/
这道是hard，基本上是用Union Find最好。

参考着https://blog.csdn.net/johnny901114/article/details/80721436
，我们来顺一下Union Find的过程。

• Quick Find
• Quick Union
• 基于size的优化
• 基于rank的优化
• 路径压缩优化

Quick Find

Find的时间复杂度为 O(1)，Union的时间复杂度为 O(n)。如果数据量一大 O(n) 复杂度就显得很慢。

public class UnionFind {

    private int[] parents;

    public UnionFind(int size) {
        parents = new int[size];
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i; // 最开始每个节点的parent是自己
        }
    }

    private int find(int p) {
        return parents[p];
    }

    public void union(int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if (qID == pID) { //如果本身就是相连的
            return;
        }
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == pID) {
                parents[i] = qID;
            }
        }
    }
}

Quick Union

Find的时间复杂度为 O(h)，Union的时间复杂度为 O(h)。h是树的高度。相对 Quick Find 实现的并查集 Quick Union 实现的并查集牺牲了一点查找的性能，提高了合并的性能。

public class UnionFind {

    private int[] parents;

    public UnionFind(int size) {
        parents = new int[size];
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }
    }

    private int find(int p) {
        while (p != parents[p]) {
            p = parents[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot)  {
            return;
        }
        parents[pRoot] = qRoot;
    }
}

基于size的优化

上面Quick Union版本的并查集基于树形结构实现的，但是没有对树的高度进行任何优化和限制。所以导致在上面的性能比对中 Quick Union 的并查集性能很差。

public class UnionFind {
    private int[] parents;
    private int[] sz; // 记录每棵树的节点个数

    public UnionFind(int size) {
        parents = new int[size];
        sz = new int[size];
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
            sz[i] = 1; // 每个根节点的一开始都只有一个节点
        }
    }

    private int find(int p) {
        while (p != parents[p]) {
            p = parents[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //根据根节点的子节点个数来判断合并方向
        if (sz[pRoot] < sz[qRoot]) {
            parents[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        } else {
            parents[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}

基于rank的优化

上面基于size的优化方案，是节点数少的树往节点数多的树合并。但是节点数多不代表树的高度高。

public class UnionFind {
private int[] parents;
    // rank[i]表示i为根的集合所表示的树的层数
    private int[] rank;

    public UnionFind(int size) {
        parents = new int[size];
        rank = new int[size];
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
            // 每个根节点所在的树一开始都只有一个层
            rank[i] = 1;
        }
    }

    private int find(int p) {
        while (p != parents[p]) {
            p = parents[p];
        }
        return p;
    }

    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        // 根据根节点所在树的层级来判断合并方向
        // 层级矮的树往层级高的树合并不需要维护rank
        if (rank[pRoot] < rank[qRoot]) {
            parents[pRoot] = qRoot;
        } else if (rank[pRoot] > rank[qRoot]) {
            parents[qRoot] = pRoot;
        } else { // 只有rank相等的情况才需要维护rank
            parents[pRoot] = qRoot;
            rank[qRoot] += 1;
        }
    }
}

路径压缩优化

路径压缩基于rank的基础上来做优化的。优化时机是在执行 find操作 的时候对其进行路径压缩。

private int find(int p) {
    while (p != parents[p]) {
        parents[p] = parents[parents[p]];
        p = parents[p];
    }
    return p;
}

对于Union操作，如果同时使用了path compression和union by rank，时间复杂度是常数。