欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

java并查集算法帶你領(lǐng)略熱血江湖

 更新時間:2021年11月09日 10:07:21   作者:愛敲代碼的小黃  
這篇文章主要為大家介紹了java并查集算法,以大家熱愛的方式,帶你領(lǐng)略熱血江湖中的并查集算法,有需要的朋友可以借鑒參考下,希望能夠有所幫助

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

一、什么是并查集

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

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

當然,這樣的定義讓人感覺摸不著頭腦,我們來一個樣例進行分析。

二、深入理解并查集

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

  • 1號:擅長刀、武力值98
  • 2號:擅長劍、武力值95
  • 3號:擅長棍、武力值93
  • 4號:擅長槍、武力值90

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

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

江湖的局面被五人分割,如下圖所示:

  • 箭頭的含義:自己的大哥(比如2號的箭頭指向自己,那2號的大哥就是他自己)

在這里插入圖片描述

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

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

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

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

在這里插入圖片描述

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

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

至此,江湖只存在兩個派系,2號派系、小黃派系。

2號察覺到了目前小黃的勢力,主動擺宴,希望江湖不在打打殺殺,能夠平安無事。

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

在這里插入圖片描述

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

并查集的初始化:

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

    // 初始化
    // 每個人的大哥都是自己
    // 每個隊伍的人數(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) 方法:這里的時間復(fù)雜度可以降低到O(1)級別,不敢相信吧,那就往下看吧。

	// 查詢a和b在不在一個陣營中
	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)方法:先去找到兩個參數(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行路徑壓縮優(yōu)化。

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

如下所示:

在這里插入圖片描述

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

如果我們在進行查找的時候,保存一下值,然后重新掛到1的上面,比如:

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

在這里插入圖片描述

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

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 專欄:并查集

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

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

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

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

相關(guān)文章

  • Feign 集成 Hystrix實現(xiàn)不同的調(diào)用接口不同的設(shè)置方式

    Feign 集成 Hystrix實現(xiàn)不同的調(diào)用接口不同的設(shè)置方式

    這篇文章主要介紹了Feign 集成 Hystrix實現(xiàn)不同的調(diào)用接口不同的設(shè)置方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • Java集合ArrayDeque類實例分析

    Java集合ArrayDeque類實例分析

    這篇文章主要介紹了Java集合ArrayDeque類實例分析的相關(guān)資料,需要的朋友可以參考下
    2017-04-04
  • java springmvc亂碼解決歸納整理詳解

    java springmvc亂碼解決歸納整理詳解

    本篇文章介紹了java 中spring mvc 解決亂碼的問題方法實例,需要的朋友可以參考下
    2017-04-04
  • java中的通用權(quán)限管理設(shè)計(推薦)

    java中的通用權(quán)限管理設(shè)計(推薦)

    下面小編就為大家推薦一篇java中的通用權(quán)限管理設(shè)計,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2017-12-12
  • idea修改maven模塊名稱還顯示老名稱問題解決

    idea修改maven模塊名稱還顯示老名稱問題解決

    本文主要介紹了idea修改maven模塊名稱還顯示老名稱問題解決,文中通過圖文介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-11-11
  • java基礎(chǔ)之反射和泛型以及注解

    java基礎(chǔ)之反射和泛型以及注解

    這篇文章主要介紹了 java基礎(chǔ)之反射和泛型以及注解的相關(guān)資料,需要的朋友可以參考下
    2017-07-07
  • swagger2隱藏在API文檔顯示某些參數(shù)的操作

    swagger2隱藏在API文檔顯示某些參數(shù)的操作

    這篇文章主要介紹了swagger2隱藏在API文檔顯示某些參數(shù)的操作,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • Spring?Cloud?Ribbon?負載均衡使用策略示例詳解

    Spring?Cloud?Ribbon?負載均衡使用策略示例詳解

    Spring?Cloud?Ribbon?是基于Netflix?Ribbon?實現(xiàn)的一套客戶端負載均衡工具,Ribbon客戶端組件提供了一系列的完善的配置,如超時,重試等,這篇文章主要介紹了Spring?Cloud?Ribbon?負載均衡使用策略示例詳解,需要的朋友可以參考下
    2023-03-03
  • 深入解析Java的Hibernate框架中的持久對象

    深入解析Java的Hibernate框架中的持久對象

    Hibernate的持久對象在數(shù)據(jù)庫數(shù)據(jù)操作中有著重要作用,這里我們就來深入解析Java的Hibernate框架中的持久對象,首先必須從理解持久化對象的生命周期開始:
    2016-07-07
  • JAVA  靜態(tài)的單例的實例詳解

    JAVA 靜態(tài)的單例的實例詳解

    這篇文章主要介紹了JAVA 靜態(tài)的單例的實例詳解的相關(guān)資料,這里提供了實例方法,來說名不僅實現(xiàn)了延遲加載,又可以保證線程安全,不影響系統(tǒng)性能,需要的朋友可以參考下
    2017-07-07

最新評論