java并查集算法帶你領略熱血江湖
你好，我是小黃，一名獨角獸企業(yè)的Java開發(fā)工程師。
校招收獲數(shù)十個offer，年薪均20W~40W。
感謝茫茫人海中我們能夠相遇，
俗話說：當你的才華和能力，不足以支撐你的夢想的時候，請靜下心來學習，
希望優(yōu)秀的你可以和我一起學習，一起努力，實現(xiàn)屬于自己的夢想。
一、什么是并查集
并查集被很多OIer認為是最簡潔而優(yōu)雅的數(shù)據(jù)結構之一，主要用于處理一些不相交集合的合并問題，并支持兩種操作：
- 合并（Union）：把兩個不相交的集合合并為一個集合。
- 查詢（Find）：查詢兩個元素是否在同一個集合中。
當然，這樣的定義讓人感覺摸不著頭腦，我們來一個樣例進行分析。
二、深入理解并查集
在遙遠的江湖，有一群武俠人，他們各自為戰(zhàn)，守護著自己該守護的東西。
- 1號：擅長刀、武力值98
- 2號：擅長劍、武力值95
- 3號：擅長棍、武力值93
- 4號：擅長槍、武力值90
突然有一天，一個不速之客（小黃）來到了這個江湖，想要稱霸江湖，一場腥風血雨的戰(zhàn)斗即將拉開序幕。
- 小黃：擅長機關槍、武力值100、寶物：并查集
江湖的局面被五人分割，如下圖所示：
- 箭頭的含義：自己的大哥（比如2號的箭頭指向自己，那2號的大哥就是他自己）
小黃看到其余4人的資料后，使用寶物并查集查詢了一下4號和其余幾人的關系，發(fā)現(xiàn)4號是孤膽一人， 決定從4號先入手。
在一個月黑風高的晚上，小黃拿著機關槍，使用寶物并查集的合并，把4號進行收服，成為其小弟。
1號、2號、3號聽聞昨夜4號被收服，立刻舉行會議商討合作的事情，1號由于身高氣傲，不想要與另外兩人合作，2號、3號只好進行合作。
于是，江湖的局面又發(fā)生了變化。
小黃的野心可是稱霸江湖，于是使用寶物并查集分別查詢了1號、2號、3號的目前狀態(tài)，得知：1號還是獨膽一人，而2、3號已經結盟。
小黃又在一個夜黑風高的晚上與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） 方法：這里的時間復雜度可以降低到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--;
}
}
四、真題訓練
初始化數(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)化
我們目前的并查集已經可以解決大部分問題，但是，我們能夠對目前的并查集版本進行路徑壓縮優(yōu)化。
我們可以發(fā)現(xiàn)，在我們 find() 方法時，我們會進行一個 while() 循環(huán)的查找大哥的操作，這種操作十分的浪費時間，有沒有什么辦法可以進行下優(yōu)化呢？
如下所示：
我們可以看到對于6、5、3之類來說，每次進行 find 查詢的時候，都需要經過2~3次的循環(huán)才能夠找到1。
如果我們在進行查找的時候，保存一下值，然后重新掛到1的上面，比如：
我要查詢下6，肯定會查詢找5、3，這個時候，我們把6、5、3保存到臨時數(shù)組中，在查詢完畢后，將這些數(shù)組直接掛到1的下面，這樣的話，下次查詢會降低循環(huán)的次數(shù)。
當我們查詢的次數(shù)遠遠大于我們的數(shù)據(jù)量時，這個時候 find() 的操作就已經變成了一個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;
}
六、總結
并查集算法通常用在處理一些不交集（Disjoint Sets）的合并及查詢問題
力扣也有并查集的 tag 專欄：并查集
大家可以好好體會一下路徑壓縮的奇妙，通過不斷的路徑壓縮，可以將我們的時間復雜度降低到O(1)
這里可能有小伙伴有疑問，為啥是O(1)，你就算掛在1的下面，不也得查詢兩次嘛
對于時間復雜度來說，只要是常數(shù)的次數(shù)都可以認定為O(1)的時間復雜度，況且，你也可以使用HashMap來進行存儲。
以上就是java并查集算法帶你領略熱血江湖的詳細內容，更多關于java并查集算法的資料請關注腳本之家其它相關文章！
相關文章
Feign 集成 Hystrix實現(xiàn)不同的調用接口不同的設置方式
這篇文章主要介紹了Feign 集成 Hystrix實現(xiàn)不同的調用接口不同的設置方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
這篇文章主要介紹了Java集合ArrayDeque類實例分析的相關資料,需要的朋友可以參考下2017-04-04
本篇文章介紹了java 中spring mvc 解決亂碼的問題方法實例，需要的朋友可以參考下2017-04-04
下面小編就為大家推薦一篇java中的通用權限管理設計，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2017-12-12
本文主要介紹了idea修改maven模塊名稱還顯示老名稱問題解決,文中通過圖文介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-11-11
這篇文章主要介紹了 java基礎之反射和泛型以及注解的相關資料,需要的朋友可以參考下2017-07-07
swagger2隱藏在API文檔顯示某些參數(shù)的操作
這篇文章主要介紹了swagger2隱藏在API文檔顯示某些參數(shù)的操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
Spring?Cloud?Ribbon?負載均衡使用策略示例詳解
Spring?Cloud?Ribbon?是基于Netflix?Ribbon?實現(xiàn)的一套客戶端負載均衡工具，Ribbon客戶端組件提供了一系列的完善的配置，如超時，重試等，這篇文章主要介紹了Spring?Cloud?Ribbon?負載均衡使用策略示例詳解,需要的朋友可以參考下2023-03-03
Hibernate的持久對象在數(shù)據(jù)庫數(shù)據(jù)操作中有著重要作用,這里我們就來深入解析Java的Hibernate框架中的持久對象,首先必須從理解持久化對象的生命周期開始:2016-07-07
這篇文章主要介紹了JAVA 靜態(tài)的單例的實例詳解的相關資料,這里提供了實例方法，來說名不僅實現(xiàn)了延遲加載，又可以保證線程安全，不影響系統(tǒng)性能，需要的朋友可以參考下2017-07-07