有序表并查集

来源 左神 有序表并查集

并查集

岛问题

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

【举例】
001010
111010
100100
000000
这个矩阵中有三个岛

遍历二维数组每一位， 如果这一位为1，就调用感染函数进行感染（周围的岛屿都变为2），记录了调用几次感染函数,就有几个岛屿。

public class CountIslands {

    /*
    定义 遍历二维数组每一位， 如果这一位为1，就调用感染函数进行感染，最后记录了调用几次感染函数
     */
    public int numIslands(char[][] 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') {
                    res++;
                    infect(m, i, j, N, M);
                }
            }
        }
        return res;
    }

    // 感染函数， 感染这个数值周围所有的联通 dfs
    private void infect(char[][] m, int i, int j, int N, int M) {
        if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != '1') {
            return;
        }
        // i，j没有越界，并且都为1
        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);
    }

    public static void main(String[] args) {
        char[][] m = {{'0', '0', '1', '0', '1', '0'},
                {'1', '1', '1', '0', '1', '0'},
                {'1', '0', '0', '1', '0', '0'},
                {'0', '0', '0', '0', '0', '0'}};
        System.out.println(new CountIslands().numIslands(m));
    }
}

时间复杂度：在遍历阶段，每个位置遍历一次，感染阶段，每个位置只遍历4次（上下左右调用），O(n*m)。

如何设计一个并行算法解决这个问题？

并查集介绍

1. 并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。

2. 并查集通常包含两种操作

   • init(s)：建立一个新的并查集，其中包含s个单元素集合
   • union(x, y)：把元素x和元素y所在的集合合并，要求x和y所在的集合不相交，如果相交则不合并
   • find(x)：找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了

find(D)和find(F)分别返回元素D和元素F所属集合的代表A和H：

union(D, F)将元素D和元素F所在的集合合并：

public class UnionFind {

    // 样本进来会包一层，叫做元素
    public static class Element<V> {
        public V value;

        public Element(V value) {
            this.value = value;
        }
    }

    public static class UnionFindSet<V> {

        public HashMap<V, Element<V>> elementMap;
        // key某个元素value该元素的父
        public HashMap<Element<V>, Element<V>> fatherMap;
        // key某个集合的代表元素value该集合的大小
        public HashMap<Element<V>, Integer> sizeMap;

        public UnionFindSet(List<V> list) {
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V val : list) {
                Element<V> element = new Element<>(val);
                elementMap.put(val, element);
                fatherMap.put(element, element);
                sizeMap.put(element, 1);
            }
        }

        // 给定一个ele，往上一直找，把代表元素返回
        private 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;
        }

        // 是否是同一个集合
        public boolean isSameSet(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
            }
            return false;
        }

        // 联合2个集合
        public void union(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                Element<V> af = findHead(elementMap.get(a));
                Element<V> bf = findHead(elementMap.get(b));
                // 如果两个元素不是同一个父
                if (af != bf) {
                    // 数量少的集合要挂在数量多集合的下面
                    Element<V> big = sizeMap.get(af)>=sizeMap.get(bf) ? af : bf;
                    Element<V> small = big == af ? af : bf;
                    // 更新 small的父节点为big
                    fatherMap.put(small, big);
                    // 更新各自集合的尺寸
                    sizeMap.put(big, sizeMap.get(af) + sizeMap.get(bf));
                    sizeMap.remove(small);
                }
            }
        }
    }
}

单次时间复杂度可以是O(1)

并查集解决岛问题

class Solution {
    public int row, col;
    public int numIslands(char[][] grid) {
        row = grid.length;
        col = grid[0].length;
        int n = row * col;
        int ocean = 0;
        UnionFind uf = new UnionFind(n);

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '0') {
                    ocean += 1;
                } else {
                    if (i > 0 && grid[i - 1][j] == '1') uf.union(node(i, j), node(i - 1, j));
                    if (j > 0 && grid[i][j - 1] == '1') uf.union(node(i, j), node(i, j - 1));
                    if (i < row - 1 && grid[i + 1][j] == '1') uf.union(node(i, j), node(i + 1, j));
                    if (j < col - 1 && grid[i][j + 1] == '1') uf.union(node(i, j), node(i, j + 1));
                }
            }
        }
        return uf.size - ocean;
    }
    int node (int i, int j) {
        return i * col + j;
    }
}

class UnionFind {
    int[] roots;
    int size;   // 岛屿数量

    public UnionFind(int n) {
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
        size = n;
    }

    public int find(int i) {
        while (i != roots[i]) {
            roots[i] =roots[roots[i]];
            i = roots[i];
        }
        return i;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
            size--;
        }
    }
}

当使用并查集在多个cpu上计算岛屿，将矩阵拆分为多块，每块各自使用感染算法计算各自的的岛屿，并记录各自块的边界上的岛屿的联通情况（land[i][j] = a），当所有块的岛屿计算完成后，在根据边界上的岛屿如果联通，就合并为一个集合。

并查集题