Leetcode之Union-Find(并查集)

roland_reed 發(fā)布于2019-08-15 13:44 / 2384人閱讀

摘要：并查集包括查詢和聯(lián)合，主要使用不相交集合查詢主要是用來決定不同的成員是否在一個子集合之內(nèi)聯(lián)合主要是用來把多個子集合成一個集合的實際運用計算機網(wǎng)絡(luò)檢查集群是否聯(lián)通電路板檢查不同的電路元件是否聯(lián)通初始化聯(lián)通與檢測與是否聯(lián)通返回聯(lián)通的數(shù)

并查集(Union-Find)包括查詢(Find)和聯(lián)合(Union)，主要使用不相交集合(Disjoint-Sets)
查詢(Find)主要是用來決定不同的成員是否在一個子集合之內(nèi)
聯(lián)合(Union)主要是用來把多個子集合成一個集合
Union-Find的實際運用：
1.計算機網(wǎng)絡(luò)檢查集群是否聯(lián)通 2.電路板檢查不同的電路元件是否聯(lián)通

Union-Find(mainly used for detection of connectivity problem):

Public Class UF:
    UF(int n) //初始化(abstract N sites : list of integers to 0,1,2 .. N-1)
    Void Union(int a, int b) //聯(lián)通a與b(add connection between a and b)
    int find(int a) //component identifier
    boolean isConnected(int a, int b) //檢測a與b是否聯(lián)通
    int count() //返回聯(lián)通的數(shù)量(return number of connected components)

舉個例子：
Given Objects: 0, 1, 2, 3, 4, 5
union(0, 1):
0-1, 2, 3, 4, 5
union(1,3):
0-1-3, 2, 4, 5
union(2,5):
0-1-3, 2-5, 4
union(3, 5):
0-1-3-2-5, 4

Union-Find在計算機算法面試主要用來解決動態(tài)圖(Dynamic Graph)的一系列問題:
例如：一個由0與1組成的二維矩陣，0可以看成海洋，1可以看成陸地
110101
001011
101011
100110
Q1:有多少島？4(dfs,bfs),靜態(tài)圖(static graph)
Q2:湖(上下左右不包換對角線被陸地包圍)的面積有多少? 2(dfs, bfs),靜態(tài)圖
Q3:如果改變圖中的元素有多少島?(0,0):5; (0,1):5; (0, 5): 6; (1,5): 5, 動態(tài)圖(Dynamic Graph)

Union-Find的種類：
Quick UnionFind(Quick-Union)

class QuickUnion:
    private int[] ids;
    public QuickUnionFind(int n):
        ids = new int[n];
        for(int i = 0; i < n; i++) {
            ids[i] = i;
        }
    }
    public void union(int a, int b) {
        int idA = ids[a];
        int idB = ids[b];
        for(int i = 0; i < n; i++) {
            if(ids[i] == idB){ //聯(lián)通所有與A聯(lián)通的元素
                ids[i] = idA;
            }
        }
    }
    public boolean find(int a, int b) {
        return ids[a] == ids[b];
    }
 }

比如，如果想要連通id[5]與id[9], 需要在union的過程中遍歷所有與id5連通的元素將下標(biāo)改成id9，或者將所有id9的下標(biāo)改成id5

QuickUnion的遍歷需要通過一次的數(shù)組讀取來找到對應(yīng)的節(jié)點，但是對于新增路徑需要需要線性時間找到對應(yīng)的組號進(jìn)行修改，所以對于大數(shù)據(jù)量來說如果新增路徑數(shù)量是M，節(jié)點的數(shù)量是N，我們需要O(MN)的時間復(fù)雜度來尋找對應(yīng)的標(biāo)號然后修改，平方的時間復(fù)雜度是非常費時的，所以我們需要提高Union的效率

Tree Union Find
QuickUnion之所以Union的時間復(fù)雜度比較高主要是因為對于每個節(jié)點的所屬的組都是多帶帶記錄，因此需要一種更優(yōu)化的數(shù)據(jù)結(jié)構(gòu)來快速更新節(jié)點所屬的組，因此我們可以用一個parent node來連接所有的sub node形成樹來降低Union的時間

使用parent-link將子節(jié)點與根節(jié)點連接，id[a]的值就是父節(jié)點的序號，因此通過查找，總可以從一個子節(jié)點查找到根節(jié)點(id[a] == a)，因此在處理不同組的時候，我們只需要找到每個元素的根節(jié)點然后更新根節(jié)點的指向就可以了，就相當(dāng)于將其中一個根節(jié)點所代表的樹變成另外一個根節(jié)點的子樹

class TreeUnionFind:
    private int[] ids;
    public TreeUnionFind(int n) {
        ids = new int[n];
        for(int i = 0; i < n; i++) {
            ids[i] = i;
        }
    }
    public int root(int a) {
        int root = a;
        while(ids[root] != root) {
                ids[root] = root;
        }
    }
    public boolean find(int a, int b) {
        return root(a) == root(b);
    }
    public void union(int a, int b) {
        int rootA = ids[a];
        int rootB = ids[b];
        ids[rootA] = rootB;
    }
}

但是樹這種數(shù)據(jù)結(jié)果經(jīng)常會根據(jù)輸入數(shù)據(jù)本身的性質(zhì)而變化，如果輸入數(shù)據(jù)是有序的相對應(yīng)的樹會變成一個單一鏈表因而不具備范性的運用情況

Weighted Quick Union Find

根據(jù)Quick-Union Find:

    public void union(int a, int b) {
        int idA = ids[a];
        int idB = ids[b];
        for(int i = 0; i < n; i++) {
            if(ids[i] == idB){ 
                ids[i] = idA;
            }
        }
    }

ids[i] = idA是一種hard code的習(xí)慣，因為random assign一棵樹是另外一棵樹的子樹沒有考慮輸入數(shù)據(jù)的規(guī)模，如果輸入數(shù)據(jù)p與q，如果p數(shù)據(jù)所在樹的規(guī)模比q數(shù)據(jù)所在樹的規(guī)模大得多，p與q新形成的樹不是平衡樹

因此，需要總是需要用小的size的樹與大的size的樹合并從而盡量達(dá)到樹的平衡

class WeightedQuickUnionFind{
    private int[] ids;
    private int[] sizes;
    public WeightedQuickUnionFind(int n) {
        ids = new int[n];
        sizes = new int[n]; //在quickUnion的基礎(chǔ)上增加一個記錄size的變量
        for(int i = 0; i < n; i++) {
            ids[i] = i;
            sizes[i] = 1;//初始化size的大小為1
        }
    }
    public int root(int a, int b) {
        int root = a;
        while(ids[root] != root) {
            root = ids[root];
        }
        return root;
    }
    public void union(int a, int b) {
        int rootA = ids[a];
        int rootB = ids[b];
        if(sizes[rootA] > sizes[rootB]) { //判斷size的大小來更新root
            ids[rootB] = rootA;
            sizes[rootA] += sizes[rootB];
        } else {
            ids[rootA] = rootB;
            sizes[rootB] += sizes[rootA];
        } 
    }
 }

通過weightedQuickUnion, 可以通過O(logn)的時間復(fù)雜度來分別Union和Find所需要的元素

Weighted QuickUnion With Path Compression
在Weighted QuickUnion的基礎(chǔ)上我們可以通過路徑壓縮(path compression)就是把所有的元素下標(biāo)直接連接到父節(jié)點來達(dá)到降低Union和Find時間復(fù)雜度的目的

class weightedQuickUnionWithPathCompression{
    private int[] ids;
    private int[] sizes;
    public weightedQuickUnionWithPathCompression(int n) {
        ids = new int[n];
        sizes = new int[n];
        for(int i = 0; i < n; i++) {
            ids[i] = i;
            sizes[i] = 1;
        }
    }
    public int root(int a, int b) {
        int root = a;
        while(ids[root] != root) {
            root = ids[root];
        }
        while(a != root) { //connect sub element directly to root
            int temp = ids[a];
            ids[a] = root;
            a = temp;
        }
        return root;
    }
    public boolean find(int a, int b) {
        return root(a) == root(b);
    }
    public boolean union(int a, int b) {
        int rootA = ids[a];
        int rootB = ids[b];
        if(sizes[rootA] > sizes[rootB]) {
            ids[rootB] = rootA;
            sizes[rootA] += sizes[rootB];
        } else {
            ids[rootA] = ids[rootB];
            sizes[rootB] += sizes[rootA];
        }
    }
 }

由此，以上就是所有關(guān)于動態(tài)連接的UnionFind的介紹，下圖是不同思路并查集的算法時間復(fù)雜度對比：
Algorithm
Quick UnionFind: Construct: O(n); Find: O(1); Union:O(n)
Tree UnionFind: Construct: O(n); Find: O(tree height); Union:O(n)
Weighted QuickUnionFind:Construct: O(n); Find: O(logn); Union:O(logn)
Weighted QuickUnionFind with Path Compression: Construct: O(n); Find: amortizedO(1); Union:amortizedO(1)

leetcode里使用UnionFind的題主要有:Number of Islands(lc200), LongestConsecutiveSequence(lc128), SurroundedRegion(lc130)

Surrounded Region:
Given a 2D board containing "X" and "O" (the letter O), capture all regions surrounded by "X".A region is captured by flipping all "O"s into "X"s in that surrounded region.
For Example:
XXXX
XOOX
XXOX
XOXX
After should become:
XXXX
XXXX
XXXX
XOXX

class Solution{
    public void solve(char[][] board) {
        //sanity check
        if(board == null || board.length == 0) return;
        int row = board.length;
        int col = board[0].length;
        int dummy = row * col; //create a dummy node to represent list of nodes
        UnionFind uf = new UnionFind(row * col + 1);
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(board[i][j] == "O") {
                    if(i == 0 || i == row - 1 || j == 0 || j == col - 1) {
                        uf.union(node(i, j), dummy); //connect corner nodes
                    } else {
                        if(i > 0 && board[i-1][j] == "O") uf.union(node(i, j), node(i-1, j));
                        if(i > 0 && board[i+1][j] == "O") uf.union(node(i, j), node(i-1, j));
                        if(j > 0 && board[i][j-1] == "O") uf.union(node(i, j), node(i, j-1));
                        if(j > 0 && board[i][j+1] == "O") uf.union(node(i, j), node(i, j+1));
                    }
                }
            }
         }
         for(int i = 0; i < row; i++) {
             for(int j = 0; j < col; j++) {
                 if(uf.isConnected(board[i][j], dummy)) board[i][j] = "O";
                 else board[i][j] = "X";
             }
         }
      }
      public int node(int i, int j) {
          return i * col + j;//convert 2d dimension to 1d
      }
 }
 class UnionFind{
     int[] parents;
     public UnionFind(int[] n) {
         parents = new int[n];
         for(int i = 0; i < n; i++) {
             parents[i] = i;
         }
     }
     public void union(int i, int j) {
         int rootA = find(i);
         int rootB = find(j);
         if(rootA != rootB) {
             parents[rootA] = rootB;
         }
     }
     public int find(int node) {
         if(parents[node] == node) return node;
         parents[node] = find(parents[node]);
         return parents[node];
     }
     public boolean isConnected(int n1, int n2) {
         return find(n1) == find(n2);
     }
}

References:
1.https://algs4.cs.princeton.ed...

2.http://blog.csdn.net/dm_vince...

云服務(wù)器 GPU云服務(wù)器并查集 union-find LeetCode LeetCode_String

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68283.html

發(fā)表評論

登陸后可評論

0條評論

roland_reed

男|高級講師

我要關(guān)注我要私信

TA的文章

CSS選擇器之:nth-child(n)與:nth-last-of-type(number)

閱讀 1062·2019-08-30 12:57
前端每日實戰(zhàn) 169# 視頻演示如何制作“數(shù)略詞”交互動畫（內(nèi)含2個視頻）

閱讀 2149·2019-08-30 11:11
GridManager 隱藏列

閱讀 2187·2019-08-29 15:20
【Angular】Angular 2+ 樣式綁定解析

閱讀 1879·2019-08-29 14:12
前端開發(fā)面試題

閱讀 3282·2019-08-28 17:51
Image Load Error Handler

閱讀 2387·2019-08-26 13:23
NAT穿越下的STUN,TURN和ICE

閱讀 809·2019-08-26 10:34
vue組件：canvas實現(xiàn)圖片涂鴉功能

閱讀 3870·2019-08-23 12:37

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

Leetcode之Union-Find(并查集)

相關(guān)文章

leetcode200. Number of Islands

Union-Find并查集算法學(xué)習(xí)筆記

**[Leetcode] Graph Valid Tree 圖與樹**

Tensorflow代碼解析（四）

**[Leetcode] Graph Valid Tree 判斷一個圖是否為樹**

發(fā)表評論

0條評論

roland_reed

男|高級講師

TA的文章

CSS選擇器之:nth-child(n)與:nth-last-of-type(number)

前端每日實戰(zhàn) 169# 視頻演示如何制作“數(shù)略詞”交互動畫（內(nèi)含2個視頻）

GridManager 隱藏列

【Angular】Angular 2+ 樣式綁定解析

前端開發(fā)面試題

Image Load Error Handler

NAT穿越下的STUN,TURN和ICE

vue組件：canvas實現(xiàn)圖片涂鴉功能

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

Leetcode之Union-Find(并查集)

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！