你好，我是小黃，一名獨(dú)角獸企業(yè)的Java開發(fā)工程師。
校招收獲數(shù)十個(gè)offer，年薪均20W~40W。
感謝茫茫人海中我們能夠相遇，
俗話說：當(dāng)你的才華和能力，不足以支撐你的夢想的時(shí)候，請靜下心來學(xué)習(xí)，
希望優(yōu)秀的你可以和我一起學(xué)習(xí)，一起努力，實(shí)現(xiàn)屬于自己的夢想。

一、什么是并查集

并查集被很多OIer認(rèn)為是最簡潔而優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)之一，主要用于處理一些不相交集合的合并問題，并支持兩種操作：

• 合并（Union）：把兩個(gè)不相交的集合合并為一個(gè)集合。
• 查詢（Find）：查詢兩個(gè)元素是否在同一個(gè)集合中。

當(dāng)然，這樣的定義讓人感覺摸不著頭腦，我們來一個(gè)樣例進(jìn)行分析。

二、深入理解并查集

在遙遠(yuǎn)的江湖，有一群武俠人，他們各自為戰(zhàn)，守護(hù)著自己該守護(hù)的東西。

• 1號(hào)：擅長刀、武力值98
• 2號(hào)：擅長劍、武力值95
• 3號(hào)：擅長棍、武力值93
• 4號(hào)：擅長槍、武力值90

突然有一天，一個(gè)不速之客（小黃）來到了這個(gè)江湖，想要稱霸江湖，一場腥風(fēng)血雨的戰(zhàn)斗即將拉開序幕。

• 小黃：擅長機(jī)關(guān)槍、武力值100、寶物：并查集

江湖的局面被五人分割，如下圖所示：

• 箭頭的含義：自己的大哥（比如2號(hào)的箭頭指向自己，那2號(hào)的大哥就是他自己）
  

小黃看到其余4人的資料后，使用寶物并查集查詢了一下4號(hào)和其余幾人的關(guān)系，發(fā)現(xiàn)4號(hào)是孤膽一人， 決定從4號(hào)先入手。

在一個(gè)月黑風(fēng)高的晚上，小黃拿著機(jī)關(guān)槍，使用寶物并查集的合并，把4號(hào)進(jìn)行收服，成為其小弟。

1號(hào)、2號(hào)、3號(hào)聽聞昨夜4號(hào)被收服，立刻舉行會(huì)議商討合作的事情，1號(hào)由于身高氣傲，不想要與另外兩人合作，2號(hào)、3號(hào)只好進(jìn)行合作。

于是，江湖的局面又發(fā)生了變化。

小黃的野心可是稱霸江湖，于是使用寶物并查集分別查詢了1號(hào)、2號(hào)、3號(hào)的目前狀態(tài)，得知：1號(hào)還是獨(dú)膽一人，而2、3號(hào)已經(jīng)結(jié)盟。

小黃又在一個(gè)夜黑風(fēng)高的晚上與1號(hào)大戰(zhàn)一夜，最終使用寶物并查集的合并，收服了1號(hào)。

至此，江湖只存在兩個(gè)派系，2號(hào)派系、小黃派系。

2號(hào)察覺到了目前小黃的勢力，主動(dòng)擺宴，希望江湖不在打打殺殺，能夠平安無事。

在宴上，由于2號(hào)派系的人數(shù)小于小黃派系的人數(shù)，于是，2號(hào)派系正式被小黃派系吞噬，江湖正式統(tǒng)一。

三、實(shí)現(xiàn)并查集

并查集的初始化：

class UnionAndFind() {
    // 自己的大哥是誰
    private int[] parent;
    // 自己的隊(duì)伍有多少人
    private int[] size;
    // 江湖還有幾個(gè)派系
    int sets;

    // 初始化
    // 每個(gè)人的大哥都是自己
    // 每個(gè)隊(duì)伍的人數(shù)都為1
    public UnionAndFind(int N) {
        parent = new int[N];
        size = new int[N];
        help = new int[N];
        sets = N;
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
}

并查集的 查詢（Find） 方法：這里的時(shí)間復(fù)雜度可以降低到O(1)級(jí)別，不敢相信吧，那就往下看吧。

	// 查詢a和b在不在一個(gè)陣營中
	public boolean isSameSet(int a, int b) {
        return find(a) == find(b);
    }
	// 看一下你的最終大哥是誰
    public int find(int i){
        while(i != parent[i]){
            i = parent[i];
        }
        return i;
    }                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    

并查集的 合并（Union）方法：先去找到兩個(gè)參數(shù)的最終大哥，小弟少的大哥跟著小弟多的大哥混

	public void union(int a, int b) {
        int A = find(a);
        int B = find(b);
        if (A != B) {
            if (size[A] >= size[B]) {
                size[A] += size[B];
                parent[B] = A;
            } else {
                size[B] += size[A];
                parent[A] = B;
            }
            sets--;
        }
    }

四、真題訓(xùn)練

547. 省份數(shù)量

初始化數(shù)組，拷貝上述并查集即可

public int findCircleNum(int[][] isConnected) {
        int N = isConnected.length;
        UnionAndFind unionFind = new UnionAndFind(N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (isConnected[i][j] == 1 && i != j) {
                    unionFind.union(i, j);
                }
            }
        }
        return unionFind.sets;
    }

五、路徑壓縮優(yōu)化

我們目前的并查集已經(jīng)可以解決大部分問題，但是，我們能夠?qū)δ壳暗牟⒉榧姹具M(jìn)行路徑壓縮優(yōu)化。

我們可以發(fā)現(xiàn)，在我們 find() 方法時(shí)，我們會(huì)進(jìn)行一個(gè) while() 循環(huán)的查找大哥的操作，這種操作十分的浪費(fèi)時(shí)間，有沒有什么辦法可以進(jìn)行下優(yōu)化呢？

如下所示：

我們可以看到對于6、5、3之類來說，每次進(jìn)行 find 查詢的時(shí)候，都需要經(jīng)過2~3次的循環(huán)才能夠找到1。

如果我們在進(jìn)行查找的時(shí)候，保存一下值，然后重新掛到1的上面，比如：

我要查詢下6，肯定會(huì)查詢找5、3，這個(gè)時(shí)候，我們把6、5、3保存到臨時(shí)數(shù)組中，在查詢完畢后，將這些數(shù)組直接掛到1的下面，這樣的話，下次查詢會(huì)降低循環(huán)的次數(shù)。

當(dāng)我們查詢的次數(shù)遠(yuǎn)遠(yuǎn)大于我們的數(shù)據(jù)量時(shí)，這個(gè)時(shí)候 find() 的操作就已經(jīng)變成了一個(gè)O(1)級(jí)別的查詢時(shí)間。

public int find(int i) {
        int h = 0;
        while (i != parent[i]) {
            help[h++] = i;
            i = parent[i];
        }
        for (h--; h >= 0; h--) {
            parent[help[h]] = i;
        }
        return i;
    }

六、總結(jié)

并查集算法通常用在處理一些不交集（Disjoint Sets）的合并及查詢問題

力扣也有并查集的 tag 專欄：并查集

大家可以好好體會(huì)一下路徑壓縮的奇妙，通過不斷的路徑壓縮，可以將我們的時(shí)間復(fù)雜度降低到O(1)

這里可能有小伙伴有疑問，為啥是O(1)，你就算掛在1的下面，不也得查詢兩次嘛

對于時(shí)間復(fù)雜度來說，只要是常數(shù)的次數(shù)都可以認(rèn)定為O(1)的時(shí)間復(fù)雜度，況且，你也可以使用HashMap來進(jìn)行存儲(chǔ)。

以上就是java并查集算法帶你領(lǐng)略熱血江湖的詳細(xì)內(nèi)容，更多關(guān)于java并查集算法的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論