200: Number of Islands
题目链接:https://leetcode.com/problems/number-of-islands/
这道是medium,有三种方法:BFS, DFS, Union Find。前两种比较直接,现在着重讲一下Union Find。
Union Find算法又叫并查集算法(disjoint-set union),最常见到的用法是:检查查询两个节点的连接状态。对于它的概念和介绍可以看看这个视频:https://www.youtube.com/watch?v=YKE4Vd1ysPI
305: Number of Islands II
题目链接:https://leetcode.com/problems/number-of-islands-ii/
这道是hard,基本上是用Union Find最好。
参考着https://blog.csdn.net/johnny901114/article/details/80721436
,我们来顺一下Union Find的过程。
- Quick Find
- Quick Union
- 基于size的优化
- 基于rank的优化
- 路径压缩优化
Quick Find
Find的时间复杂度为 O(1),Union的时间复杂度为 O(n)。如果数据量一大 O(n) 复杂度就显得很慢。
public class UnionFind {
private int[] parents;
public UnionFind(int size) {
parents = new int[size];
for (int i = 0; i < parents.length; i++) {
parents[i] = i; // 最开始每个节点的parent是自己
}
}
private int find(int p) {
return parents[p];
}
public void union(int p, int q) {
int pID = find(p);
int qID = find(q);
if (qID == pID) { //如果本身就是相连的
return;
}
for (int i = 0; i < parents.length; i++) {
if (parents[i] == pID) {
parents[i] = qID;
}
}
}
}
Quick Union
Find的时间复杂度为 O(h),Union的时间复杂度为 O(h)。h是树的高度。相对 Quick Find 实现的并查集 Quick Union 实现的并查集牺牲了一点查找的性能,提高了合并的性能。
public class UnionFind {
private int[] parents;
public UnionFind(int size) {
parents = new int[size];
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
}
}
private int find(int p) {
while (p != parents[p]) {
p = parents[p];
}
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parents[pRoot] = qRoot;
}
}
基于size的优化
上面Quick Union版本的并查集基于树形结构实现的,但是没有对树的高度进行任何优化和限制。所以导致在上面的性能比对中 Quick Union 的并查集性能很差。
public class UnionFind {
private int[] parents;
private int[] sz; // 记录每棵树的节点个数
public UnionFind(int size) {
parents = new int[size];
sz = new int[size];
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
sz[i] = 1; // 每个根节点的一开始都只有一个节点
}
}
private int find(int p) {
while (p != parents[p]) {
p = parents[p];
}
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
//根据根节点的子节点个数来判断合并方向
if (sz[pRoot] < sz[qRoot]) {
parents[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
} else {
parents[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
}
基于rank的优化
上面基于size的优化方案,是节点数少的树往节点数多的树合并。但是节点数多不代表树的高度高。
public class UnionFind {
private int[] parents;
// rank[i]表示i为根的集合所表示的树的层数
private int[] rank;
public UnionFind(int size) {
parents = new int[size];
rank = new int[size];
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
// 每个根节点所在的树一开始都只有一个层
rank[i] = 1;
}
}
private int find(int p) {
while (p != parents[p]) {
p = parents[p];
}
return p;
}
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
// 根据根节点所在树的层级来判断合并方向
// 层级矮的树往层级高的树合并不需要维护rank
if (rank[pRoot] < rank[qRoot]) {
parents[pRoot] = qRoot;
} else if (rank[pRoot] > rank[qRoot]) {
parents[qRoot] = pRoot;
} else { // 只有rank相等的情况才需要维护rank
parents[pRoot] = qRoot;
rank[qRoot] += 1;
}
}
}
路径压缩优化
路径压缩基于rank的基础上来做优化的。优化时机是在执行 find操作 的时候对其进行路径压缩。
private int find(int p) {
while (p != parents[p]) {
parents[p] = parents[parents[p]];
p = parents[p];
}
return p;
}
对于Union操作,如果同时使用了path compression和union by rank,时间复杂度是常数。
网友评论