java并查集算法帶你領(lǐng)略熱血江湖
你好,我是小黃,一名獨(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)練
初始化數(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)文章!
相關(guān)文章
Feign 集成 Hystrix實(shí)現(xiàn)不同的調(diào)用接口不同的設(shè)置方式
這篇文章主要介紹了Feign 集成 Hystrix實(shí)現(xiàn)不同的調(diào)用接口不同的設(shè)置方式,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-06-06java中的通用權(quán)限管理設(shè)計(jì)(推薦)
下面小編就為大家推薦一篇java中的通用權(quán)限管理設(shè)計(jì),具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2017-12-12swagger2隱藏在API文檔顯示某些參數(shù)的操作
這篇文章主要介紹了swagger2隱藏在API文檔顯示某些參數(shù)的操作,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-06-06Spring?Cloud?Ribbon?負(fù)載均衡使用策略示例詳解
Spring?Cloud?Ribbon?是基于Netflix?Ribbon?實(shí)現(xiàn)的一套客戶端負(fù)載均衡工具,Ribbon客戶端組件提供了一系列的完善的配置,如超時(shí),重試等,這篇文章主要介紹了Spring?Cloud?Ribbon?負(fù)載均衡使用策略示例詳解,需要的朋友可以參考下2023-03-03