现在的位置: 首页 > 面试题 > 正文

并查集快速查找

2022年01月10日 面试题 ⁄ 共 952字 ⁄ 字号 暂无评论
博客主机

本小节基于上一小节并查集的结构介绍基础操作,查询和合并和判断是否连接。

 

查询元素所在的集合编号,直接返回 id 数组值,O(1) 的时间复杂度。

 

...

private int find(int p) {

assert p >= 0 && p < count;

return id[p];

}

...

合并元素 p 和元素 q 所属的集合, 合并过程需要遍历一遍所有元素, 再将两个元素的所属集合编号合并,这个过程是 O(n) 复杂度。

 

...

public void unionElements(int p, int q) {

int pID = find(p);

int qID = find(q);

if (pID == qID)

return;

for (int i = 0; i < count; i++)

if (id[i] == pID)

id[i] = qID;

}

...

Java 实例代码

源码包下载:Download

 

UnionFind1.java 文件代码:

package runoob.union;

 

/**

* 第一版union-Find

*/

public class UnionFind1 {

// 我们的第一版Union-Find本质就是一个数组

private int[] id;

// 数据个数

private int count;

 

public UnionFind1(int n) {

count = n;

id = new int[n];

// 初始化, 每一个id[i]指向自己, 没有合并的元素

for (int i = 0; i < n; i++)

id[i] = i;

}

 

// 查找过程, 查找元素p所对应的集合编号

private int find(int p) {

assert p >= 0 && p < count;

return id[p];

}

 

// 查看元素p和元素q是否所属一个集合

// O(1)复杂度

public boolean isConnected(int p, int q) {

return find(p) == find(q);

}

 

// 合并元素p和元素q所属的集合

// O(n) 复杂度

public void unionElements(int p, int q) {

 

int pID = find(p);

int qID = find(q);

 

if (pID == qID)

return;

 

// 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并

for (int i = 0; i < count; i++)

if (id[i] == pID)

id[i] = qID;

}

}

Wopus问答

【上篇】
【下篇】

Wopus问答

给我留言

留言无头像?


×