并查集
由孩子指向父親阻星，快速判斷節(jié)點(diǎn)連接狀態(tài)朋鞍。可用于解決連接問(wèn)題妥箕，就集合的并集滥酥。
集合
//interface
public interface UnionFind {
int getSize();
boolean isConnected(int p, int q);
void unionElements(int p, int q);
}
public class UnionFind1 implements UnionFind {
private int[] id;
public UnionFind1(int size) {
id = new int[size];
//每個(gè)元素都所屬不同的集合
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
}
@Override
public int getSize() {
return id.length;
}
//查找元素p所對(duì)應(yīng)的集合編號(hào)
private int find(int p){
if (p < 0 && p >= id.length)
throw new IllegalArgumentException("p is out of bound");
return id[p];
}
//查看元素p與q是否屬于同一個(gè)集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//合并元素p與元素q所屬的集合 O(n)
@Override
public void unionElements(int p, int q) {
int pId = find(p);
int qId = find(q);
if(pId == qId)
return;
for (int i = 0; i < id.length; i++) {
if (id[i] == pId)
id[i] = qId;
}
}
}
//時(shí)間復(fù)雜度 O(log^*n) 近乎于O(1)
優(yōu)化一
孩子指向父親，依然用數(shù)組表示畦幢，但是形成的是樹(shù)結(jié)構(gòu)坎吻。
union
仍然可以使用數(shù)組表示
初始狀態(tài)
union
public class UnionFind2 implements UnionFind {
private int[] parent;
public UnionFind2(int size) {
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找過(guò)程，查找元素p所對(duì)應(yīng)的集合編號(hào)
//O(h)復(fù)雜度宇葱，h為樹(shù)的高度
private int find(int p) {
if (p < 0 && p >= parent.length)
throw new IllegalArgumentException("p is out of bound");
while (p != parent[p])
p = parent[p];
return p;
}
//O(h)復(fù)雜度瘦真，h為樹(shù)的高度
//查看元素p與q是否屬于同一個(gè)集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//O(h)復(fù)雜度，h為樹(shù)的高度
//合并元素p與元素q所屬的集合 O(n)
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
parent[pRoot] = parent[qRoot];
}
}
優(yōu)化二
讓節(jié)點(diǎn)個(gè)數(shù)少的根節(jié)點(diǎn)指向節(jié)點(diǎn)個(gè)數(shù)多的根節(jié)點(diǎn)黍瞧。
優(yōu)化二
public class UnionFind3 implements UnionFind {
private int[] parent;
private int[] sz;
public UnionFind3(int size) {
parent = new int[size];
//sz[i]表示以i為根的集合中元素個(gè)數(shù)
sz = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = I;
sz[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找過(guò)程诸尽，查找元素p所對(duì)應(yīng)的集合編號(hào)
//O(h)復(fù)雜度，h為樹(shù)的高度
private int find(int p) {
if (p < 0 && p >= parent.length)
throw new IllegalArgumentException("p is out of bound");
while (p != parent[p])
p = parent[p];
return p;
}
//O(h)復(fù)雜度印颤，h為樹(shù)的高度
//查看元素p與q是否屬于同一個(gè)集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//O(h)復(fù)雜度您机，h為樹(shù)的高度
//合并元素p與元素q所屬的集合 O(n)
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
//根據(jù)倆個(gè)元素所在樹(shù)的元素個(gè)數(shù)不同判斷合并方向
//將元素個(gè)數(shù)少的集合合并到元素個(gè)數(shù)多的集合上
if(sz[pRoot] < sz[qRoot]) {
parent[pRoot] = parent[qRoot];
sz[qRoot] += sz[pRoot];
}
else { // sz[pRoot] >= sz[qRoot]
parent[qRoot] = parent[pRoot];
sz[pRoot] += sz[qRoot];
}
}
}
//時(shí)間復(fù)雜度 O(log^*n) 近乎于O(1)
優(yōu)化三
基于rank的優(yōu)化，rank[i]表示根節(jié)點(diǎn)為i的樹(shù)的高度年局。
讓深度比較少的樹(shù)向深度比較高的樹(shù)進(jìn)行合并际看。
優(yōu)化三
public class UnionFind4 implements UnionFind {
private int[] parent;
private int[] rank;
public UnionFind4(int size) {
parent = new int[size];
//rank[i]表示以i為根的集合所表示的樹(shù)的層數(shù)
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = I;
rank[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找過(guò)程，查找元素p所對(duì)應(yīng)的集合編號(hào)
//O(h)復(fù)雜度矢否，h為樹(shù)的高度
private int find(int p) {
if (p < 0 && p >= parent.length)
throw new IllegalArgumentException("p is out of bound");
while (p != parent[p])
p = parent[p];
return p;
}
//O(h)復(fù)雜度仲闽，h為樹(shù)的高度
//查看元素p與q是否屬于同一個(gè)集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//O(h)復(fù)雜度，h為樹(shù)的高度
//合并元素p與元素q所屬的集合 O(n)
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
//根據(jù)倆個(gè)元素所在樹(shù)的rank不同判斷合并方向
//將rank低的集合合并到rank高的集合上
if(rank[pRoot] < rank[qRoot]) {
parent[pRoot] = parent[qRoot];
} else if (rank[pRoot] > rank[qRoot]) {
parent[qRoot] = parent[pRoot];
}
else { // =
parent[qRoot] = parent[pRoot];
rank[pRoot] += 1;
}
}
}
//時(shí)間復(fù)雜度 O(log^*n) 近乎于O(1)
優(yōu)化四
路徑壓縮僵朗，將高樹(shù)壓縮成矮樹(shù)
優(yōu)化四
4.1
4.2
4.3
public class UnionFind5 implements UnionFind {
private int[] parent;
private int[] rank;
public UnionFind5(int size) {
parent = new int[size];
//rank[i]表示以i為根的集合所表示的樹(shù)的層數(shù)
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = I;
rank[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找過(guò)程赖欣，查找元素p所對(duì)應(yīng)的集合編號(hào)
//O(h)復(fù)雜度，h為樹(shù)的高度
// private int find(int p) {
//
// if (p < 0 && p >= parent.length)
// throw new IllegalArgumentException("p is out of bound");
//
// while (p != parent[p])
// p = parent[p];
// return p;
// }
//優(yōu)化 路徑壓縮 經(jīng)典優(yōu)化思路
//查找過(guò)程衣迷，查找元素p所對(duì)應(yīng)的集合編號(hào)
//O(h)復(fù)雜度，h為樹(shù)的高度
private int find(int p) {
if (p < 0 && p >= parent.length)
throw new IllegalArgumentException("p is out of bound");
//沒(méi)有改變r(jià)ank 使用粗略的rank值已經(jīng)能滿足性能
while (p != parent[p])
parent[p] = parent[parent[p]];
p = parent[p];
return p;
}
//O(h)復(fù)雜度酱酬，h為樹(shù)的高度
//查看元素p與q是否屬于同一個(gè)集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//O(h)復(fù)雜度壶谒，h為樹(shù)的高度
//合并元素p與元素q所屬的集合 O(n)
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
//根據(jù)倆個(gè)元素所在樹(shù)的rank不同判斷合并方向
//將rank低的集合合并到rank高的集合上
if(rank[pRoot] < rank[qRoot]) {
parent[pRoot] = parent[qRoot];
} else if (rank[pRoot] > rank[qRoot]) {
parent[qRoot] = parent[pRoot];
}
else { // =
parent[qRoot] = parent[pRoot];
rank[pRoot] += 1;
}
}
}
//時(shí)間復(fù)雜度 O(log^*n) 近乎于O(1)
優(yōu)化五
使用遞歸，將查詢的節(jié)點(diǎn)膳沽，以及其之前的節(jié)點(diǎn)都直接指向跟節(jié)點(diǎn)
優(yōu)化五
public class UnionFind6 implements UnionFind{
private int[] parent;
private int[] rank;
public UnionFind6(int size) {
parent = new int[size];
//rank[i]表示以i為根的集合所表示的樹(shù)的層數(shù)
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
//優(yōu)化 路徑壓縮 經(jīng)典優(yōu)化思路
//查找過(guò)程汗菜，查找元素p所對(duì)應(yīng)的集合編號(hào)
//O(h)復(fù)雜度让禀，h為樹(shù)的高度
private int find(int p) {
if (p < 0 && p >= parent.length)
throw new IllegalArgumentException("p is out of bound");
if (p != parent[p])
parent[p] = find(parent[p]);
return parent[p];
}
//O(h)復(fù)雜度，h為樹(shù)的高度
//查看元素p與q是否屬于同一個(gè)集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//O(h)復(fù)雜度陨界，h為樹(shù)的高度
//合并元素p與元素q所屬的集合 O(n)
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
//根據(jù)倆個(gè)元素所在樹(shù)的rank不同判斷合并方向
//將rank低的集合合并到rank高的集合上
if(rank[pRoot] < rank[qRoot]) {
parent[pRoot] = parent[qRoot];
} else if (rank[pRoot] > rank[qRoot]) {
parent[qRoot] = parent[pRoot];
}
else { // =
parent[qRoot] = parent[pRoot];
rank[pRoot] += 1;
}
}
}
//時(shí)間復(fù)雜度 O(log^*n) 近乎于O(1)
