我的笔记

🍕 并查集

岛问题

一个矩阵中只有 0 和 1 两种值, 每个位置都可以和自己的上、下、左、右四个位置相连, 如果有一片1连在一起, 这个部分叫做一个岛, 求一个矩阵中有多少个岛?

方法很简单:

遍历每个元素, 识别到 1 时, 代表碰到一个岛
此时对这个岛进行感染, 将该岛的所有元素设置为 0
感染完成后继续遍历过程, 如果又遇到一个 1, 说明这个岛肯定是新岛, 再次感染
如此反复, 最终就可以求出岛的数量

时间复杂度 O(M*N)

遍历时, 每个元素都会访问一次
感染过程时, 一个元素最多被访问四次(从上下左右四个方向访问进来)

java

int countIslands(int[][] m) {
    if (m == null || m[0] == null) {
        return 0;
    }
    int N = m.length;
    int M = m[0].length;
    int res = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (m[i][j] == 1) {
                // 每找到一个岛, 加1
                res++;
                // 同时感染这个岛, 即属于这个岛的元素, 值将不会是 1
                infect(m, i, j, N, M);
            }
        }
    }
    return res;
}

void infect(int[][] m, int i, int j, int N, int M) {
    // 感染过程也很简单, 利用递归, 因为只有四周相连, 所以不断像四个方向感染
    if (i < 0 || i >= N || j < 0 || j >= M // 防止出界
    || m[i][j] != 1) { // 不是 1, 说明是 "海"
        return;
    }
    m[i][j] = 2; // 感染
    // 继续感染四个方向
    infect(m, i+1, j, N, M);
    infect(m, i-1, j, N, M);
    infect(m, i, j+1, N, M);
    infect(m, i, j-1, N, M);
}

并查集

并查集提供的接口:

初始化, 接收一个元素列表, 每个元素初始为单独一个集合
union, 合并集合。
is_same_set, 查询是否同一集合。

经典结构实现时难以两全其美:

链表结构实现时
- 合并集合时很简单, 只需要将两条链表合并在一起, 时间复杂度是 O(1)
- 但查询是否属于同一集合时, 需要遍历这条链表, 时间复杂度是 O(N)
哈希表结构实现时
- 查询是否在同一集合时很快, 时间复杂度是 O(1)
- 合并集合时慢, 因为需要将一个集合的所有元素导入到另一个集合中, 时间复杂度是 O(N)

并查集结构, 可视化出来后就是一个向上指的图。即每一个元素都指向自己的父元素, 同一个集合中的元素会有一个代表元素。

当合并两个集合时, 只需要将一个集合的代表元素指向另一个集合的代表元素就可以了, 时间复杂度 O(1)
当查询是否在一个集合, 只需要查询代表元素是否是一个, 就可以了。时间复杂度是 O(1) 。(数学家都花了好多年证明的)
- 查询过程中有一个优化, 因为合并是将代表元素指向代表元素。所以查询时需要不断的往上找才能找到代表元素
- 优化: 在往上找的过程中, 保存遍历过的父元素, 找到代表元素后, 重新遍历这些父节点, 将他们都指向代表元素。这样下次查询时就是 O(1) 级别的。

java

// 一个样本包成一个元素
class Element<V> {
    V value;
}
class UnionFindSet<V> {
    HashMap<V, Element<V>> elementMap;
    // key 是某个元素, value 是该元素的父元素。 父元素一直往上将会到达该集合的代表元素
    HashMap<Element<V>, Element<V>> fatherMap;
    // key 是某个集合的代表元素, value 是该集合的大小
    HashMap<Element<V>, Integer> sizeMap;

    // 初始化
    UnionFindSet(List<V> list) {
        elementMap = new HashMap<>();
        fatherMap = new HashMap<>();
        sizeMap = new HashMap<>();
        for (V value : list) {
            Element<V> element = new ELement<V>(value);
            elementMap.put(value, element);
            fatherMap.put(element, element);
            sizeMap.put(element, 1);
        }
    }

    // 找到该集合所在的代表元素, 同时扁平化(查找过程中的节点全部直接指向代表元素)
    ELement<V> findHead(Element<V> element) {
        Stack<Element<V>> path = new Stack<>();
        while (element != fatherMap.get(element)) {
            path.push(element);
            element = fatherMap.get(element);
        }
        while (!path.isEmpty()) { // 扁平化
            fatherMap.put(path.pop(), element);
        }
        return element;
    }

    boolean isSameSet(V a, V b) {
        // 首先要确保这两个元素是并查集中的元素
        if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
            // 然后再查看是不是同一个集合里的
            return findHead(elementMap.get(a) == findHead(elementMap.get(b)))
        }
        return false;
    }

    void union(V a, V b) {
        if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
            Element<V> aF = findHead();
            Element<V> bF = findHead();
            if (aF != bF) {
                // 不在一个集合, 则将小集合合并到大集合中
                Element<V> big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
                Element<V> small = big == aF ? bF : aF;
                fatherMap.put(small, big);
                sizeMap.put(big, sizeMap.get(aF) + sizeMap.get(bF));
                sizeMap.remove(small);
            }
        }
    }

}

并行解决岛问题

先讨论两个 CPU 的情况, 两个 CPU, 一个负责一块区域, 查询到的岛数量肯定是大于等于实际岛数量的。多出来的岛, 是因为边界被切掉了, 所以我们的重点在于, 合并区域时, 如何处理边界上的点的信息, 以下图为例:

原始地图如下, 很明显只有一个岛

111111111111111111111111
000000000000000000111111
111111111111111111111111
111111000000000000000000
111111111111111111111111
000000000000000000111111
111111111111111111111111

切割两边后变成下面这样:

111111111111    111111111111
000000000000    000000111111
111111111111    111111111111
111111000000    000000000000
111111111111    111111111111
000000000000    000000111111
111111111111    111111111111

两个 CPU 各自处理一块, 然后会发现, 左边计算出 3 个岛, 右边计算出 2 个岛。让他们的计算的时候, 为每一个接触岛边界的点标记所在的岛, 比如用 ABCDE 表示

11111111111A    D11111111111
000000000000    000000111111
11111111111B    D11111111111
111111000000    000000000000
11111111111B    E11111111111
000000000000    000000111111
11111111111C    E11111111111

在合并的过程中, 为 ABCDE 初始化成并查集, 然后利用边界信息依次合并几个集合:

检查 A D 是否一个集合, 不在一个集合, 故合并, 此时岛的数量5-1=4
检查 B D 是否是一个集合, 不在一个集合, 故合并, 岛的数量 4-1=3
检查 B E 是否在一个集合, 不在一个集合, 故合并, 岛的数量 3-1=2
检查 C E 是否在一个集合, 不在一个集合, 故合并, 岛的数量 2-1=1
只在合并的时候岛的数量减一, 如果两个点在一个集合, 则不合并, 此时岛的数量也不会减1

这是两个 CPU 的情况, 当多个 CPU 时, 会被划分为更多的区域, 此时就会出现 4 个边界的情况, 处理方式是一样的, 只不过编程起来麻烦点。但方法要懂。

这其实一个一个 map reduce 过程, 即拆分, 然后合并。

🍕 并查集 ​

岛问题 ​

并查集 ​

并行解决岛问题 ​

🍕 并查集

岛问题

并查集

并行解决岛问题