文章目录
如果想了解并查集基础推荐去看左程云大神的算法讲解，非常不错，b站和油管上都有它的视频
1. 并查集概念
1.1 理解并查集：简介与应用场景
概述：
并查集（Disjoint Set）是一种用于处理集合合并和查询等问题的数据结构。
并查集的作用：
- 解决元素分组与连接问题
- 用于图论中的最小生成树算法、连通性问题、网络分区等
1.2 Python 实现并查集及优化策略
class UnionFind:
def __init__(self, n):
# 初始化时，每个元素的父节点为自己
self.parent = list(range(n))
# 初始化时每个树的深度为0（也可以设置为1）
self.rank = [0] * n
# 查找操作（扁平化）
def find(self, x):
if self.parent[x] != x: # 如果当前节点的父节点不是自己，说明不是根节点
# 路径压缩，将当前节点直接连接到根节点
self.parent[x] = self.find(self.parent[x])
return self.parent[x] # 返回根节点的索引
# 合并操作（小挂大）
def union(self, x, y):
root_x = self.find(x) # 找到元素 x 的根节点
root_y = self.find(y) # 找到元素 y 的根节点
if root_x != root_y: # 如果两个元素不在同一个集合中
if self.rank[root_x] < self.rank[root_y]: # 如果树的深度（秩）小于另一个树
# 将较浅的树的根节点连接到较深的树的根节点
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else: # 如果两个树深度相同，则任意连接一个到另一个，并将深度加一
self.parent[root_y] = root_x
self.rank[root_x] += 1
优化策略：
- 路径压缩优化（扁平化）：在查找操作中，将节点直接连接到根节点，降低树的深度
- 按秩合并优化（小集合挂大集合）：将深度较浅的树挂在深度较深的树下，保持树的平衡
1.3 扁平化栈实现
def find(self, x):
# 使用栈记录路径
path = []
# 找到根节点
while self.parent[x] != x:
path.append(x)
x = self.parent[x]
# 路径压缩：将路径上的所有节点直接连接到根节点
for node in path:
self.parent[node] = x
return x
1.4 分析并查集的时间复杂度
时间复杂度分析：
- 查找操作（Find）：近似为 O(1)。
- 合并操作（Union）：近似为 O(1)。
- 综合时间复杂度：近似为 O(α(n))，其中 α(n) 是 Ackermann 函数的反函数，通常视为常数级别。
2. 情侣牵手
测试链接：https://leetcode.cn/problems/couples-holding-hands/
- 分析
分析：将每对情侣的对数看成一个集合，例如：第一对情侣(0,1)，属于集合{0}；第二对情侣(2,3)，属于集合{1}...
所以最开始一定有n个集合
思路：就是每次遍历相邻的两个人，如果它们不是一对，那么它们就分别属于各自的那一对，将这两对的集合合并，此时总集合数就少1
求解答案（两种）：
1. 对于每一个集合，如果里面有m对情侣，那么就需要交换m-1次
2. 总的集合数减去合并后的集合数
例子，[0,4,2,1,3,5]：
- 一共3对情侣，3个集合，{0},{1},{2}
- 遍历0和4，0//2 != 4//2，它们不是一对，将它们的集合合并，此时有2个集合：{0,2},{1}
- 遍历2和1，2//2 != 1//2，它们不是一对，将它们的集合合并，此时有1个集合：{0,2,1}
- 所以一共需要交换：
1. 只有1个集合，这个集合有3对情侣，需要交换3-1=2次
2. 原来有3个集合，现在只有1个集合，需要交换3-1=2次
- 代码
class UnionFind:
def __init__(self, n):
self.father = [0] * n
# 初始化集合
for i in range(n):
self.father[i] = i
# 记录集合的数量
self.sets = n
def find(self, x):
if self.father[x] != x:
self.father[x] = self.find(self.father[x])
return self.father[x]
def union(self, x, y):
fx = self.find(x)
fy = self.find(y)
# 如果它们的father不相同，说明不是一对情侣，需要合并
if fx != fy:
self.father[fx] = fy
# 合并后集合数-1
self.sets -= 1
class Solution(object):
def minSwapsCouples(self, row):
"""
:type row: List[int]
:rtype: int
"""
n = len(row)
couple = UnionFind(n // 2)
for i in range(0, n - 1, 2):
# 依次遍历两个人，是一对情侣就不合并，不是一对情侣就合并
couple.union(row[i] // 2, row[i + 1] // 2)
return n // 2 - couple.sets
3. 相似字符串
测试链接：https://leetcode.cn/problems/H6lPxb/
- 题目分析
1. 什么是字母异位词？
假如给一个字符串abc，它的字母异位词有acb,bac,bca,cab,cba。当然，abc也同样是它们的字母异位词
2. 什么是相似？
给定两个字符串x，y（都由小写字母组成），分两种情况：
- 如果x和y不做任何操作就相同，那它们相似
- 如果x和y不同，交换x中任意两个字母的位置能变成y，就说明x和y相似
3. 什么是相似字符串组？
根据示例1，strs=['tars','rats','arts','star']
- 首先它们四个各自为一组，共四个组
- strs[0]和strs[1]相似，把它们分到一组
- strs[0]和strs[2]不相似，不把strs[2]加入到strs[0]那一组
- strs[0]和strs[3]不相似，不把strs[3]加入到strs[0]那一组
- strs[1]和strs[2]相似，把strs[2]加入到strs[1]那一组
- strs[1]和strs[3]不相似，不把strs[3]加入到strs[1]那一组
- ...
- strs[3]和前面的字符串都不相似，自己单独为一组
- 最后就分为了两个组，{strs[0],strs[1],strs[2]},{strs[3]}
- 很明显地就是用并查集去分组
- 只要剩余的字符串与一个组内的任一字符串相似就将它们合并
- 代码
class UnionFind:
def __init__(self, n):
self.father = [0] * n
self.size = [1] * n
for i in range(n):
self.father[i] = i
self.sets = n
def find(self, x):
if self.father[x] != x:
self.father[x] = self.find(self.father[x])
return self.father[x]
# 小挂大
def union(self, x, y):
fx = self.find(x)
fy = self.find(y)
if fx != fy:
if self.size[fx] >= self.size[fy]:
self.father[fy] = fx
self.size[fx] += self.size[fy]
else:
self.father[fx] = fy
self.size[fy] += self.size[fx]
self.sets -= 1
class Solution(object):
def numSimilarGroups(self, strs):
"""
:type strs: List[str]
:rtype: int
"""
# 共有n个字符串
n = len(strs)
# 每个字符串长度为m
m = len(strs[0])
connect = UnionFind(n)
for i in range(n):
for j in range(i + 1, n):
# 两两比较字符串，如果它们不在同一个组中，并且它们相似，就合并
if (connect.find(i) != connect.find(j)):
diff = 0
# 依次比较strs[i]和strs[j]，因为strs中的字符串都互为字母异位词
# 所以只需要看strs[i]和strs[j]有几个字符不一样就行了
for k in range(m):
if strs[i][k] != strs[j][k]:
diff += 1
# strs[i]要么完全和strs[j]一样，要么有两个字符不同，这样才满足相似的条件
if diff >= 3:
break
# 如果相似，就合并
if diff == 0 or diff == 2:
connect.union(i, j)
return connect.sets
4. 岛屿数量
测试链接：https://leetcode.cn/problems/number-of-islands/
- 分析
思路：使用并查集的话就是先将每个1都视为1个集合，如果它的上下左右也是1，就合并两个集合
下标转换：将二维下标转换为一维下标，例如下面是一个4×4的二维表，坐标[i][j]转换为一维的就是i*m + j（m为列的数量）
n\m 0 1 2 3
0 0 1 2 3
1 4 5 6 7
2 8 9 10 11
3 12 13 14 15
- 代码
class UnionFind:
def __init__(self, n, m, grid):
# 正常建立并查集，我们只需要关注“1”就行了，“0”不用管
self.father = [-1] * ((n - 1) * m + m)
self.sets = 0
for i in range(n):
for j in range(m):
if grid[i][j] == '1':
self.father[i * m + j] = i * m + j
self.sets += 1
def find(self, x):
if self.father[x] != x:
self.father[x] = self.find(self.father[x])
return self.father[x]
def union(self, x, y):
fx = self.find(x)
fy = self.find(y)
if fx != fy:
self.father[fy] = fx
self.sets -= 1
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
n = len(grid)
m = len(grid[0])
area = UnionFind(n, m, grid)
for i in range(n):
for j in range(m):
if grid[i][j] == '1':
# “0”不用管的原因是因为我们合并x,y的时候，x，y对应的二维坐标在二维表中一定是“1”
# 下面只需检查每个“1”的左上是否为1，就不用上下左右全部检查了
if j > 0 and grid[i][j - 1] == '1':
area.union(i * m + j, i * m + j - 1)
if i > 0 and grid[i - 1][j] == '1':
area.union(i * m + j, (i - 1) * m + j)
return area.sets
