难度: Hard
n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。
人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。
返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。
示例 1:
输入: row = [0,2,1,3] 输出: 1 解释: 只需要交换row[1]和row[2]的位置即可。
示例 2:
输入: row = [3,2,0,1] 输出: 0 解释: 无需交换座位，所有的情侣都已经可以手牵手了。
提示:
2n == row.length2 <= n <= 30n 是偶数0 <= row[i] < 2nrow 中所有元素均无重复运行时间: 26 ms
内存: 16.2 MB
class Solution:
def minSwapsCouples(self, row: List[int]) -> int:
class UnionSet:
def __init__(self, n = 100000):
self.father: list = list(range(n))
self.size: list = [1] * n
self.stack = []
self.set = n
def find(self, i):
while i != self.father[i]:
self.stack.append(i)
i = self.father[i]
while self.stack:
self.father[self.stack.pop()] = i
return i
def union(self, x, y):
fx = self.find(x)
fy = self.find(y)
if fx != fy:
self.set -= 1
if self.size[fx] >= self.size[fy]:
self.size[fx] += self.size[fy]
self.size[fy] = None
self.father[fy] = fx
else:
self.size[fy] += self.size[fx]
self.size[fx] = None
self.father[fx] = fy
n = len(row)
npair = n // 2
uset = UnionSet(npair)
for i in range(0, n, 2):
uset.union(row[i]//2, row[i+1]//2)
return npair - uset.set
此题解采用了并查集的数据结构来解决情侣牵手的问题。首先创建一个UnionSet类来处理并查集相关的操作，包括初始化、查找和合并。题目中的每对情侣编号为(0,1), (2,3)等，意味着两个人的ID除以2的结果如果相同，则它们是一对。算法的核心在于将每对坐在一起的情侣通过union操作合并在同一个集合中。每次合并减少一个集合，初始集合数为n对情侣即n/2。最后，需要的交换次数为初始集合数减去最后的集合数，即n/2 - uset.set。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def minSwapsCouples(self, row: List[int]) -> int:
class UnionSet:
def __init__(self, n = 100000):
self.father: list = list(range(n)) # 每个元素的父节点初始指向自己
self.size: list = [1] * n # 初始化每个集合的大小为1
self.stack = [] # 辅助栈，用于路径压缩
self.set = n # 记录并查集中集合的数量
def find(self, i):
while i != self.father[i]: # 查找根节点
self.stack.append(i)
i = self.father[i]
while self.stack: # 路径压缩
self.father[self.stack.pop()] = i
return i
def union(self, x, y):
fx = self.find(x)
fy = self.find(y)
if fx != fy: # 合并两个集合
self.set -= 1
if self.size[fx] >= self.size[fy]: # 按秩合并
self.size[fx] += self.size[fy]
self.size[fy] = None
self.father[fy] = fx
else:
self.size[fy] += self.size[fx]
self.size[fx] = None
self.father[fx] = fy
n = len(row)
npair = n // 2
uset = UnionSet(npair)
for i in range(0, n, 2):
uset.union(row[i]//2, row[i+1]//2) # 将每对坐在一起的情侣合并为一个集合
return npair - uset.set # 返回需要的最小交换次数
路径压缩技术是并查集优化中的关键技术之一，其目的是加速并查集中的查找操作。在执行查找操作时，路径压缩会将查找路径上的所有节点直接连接到根节点上，这样可以大幅减少后续查找操作的深度，从而减少查找时间。具体来说，路径压缩可以将并查集的时间复杂度几乎降为常数级，使得并查集的操作效率大大提高。
按秩合并是另一种并查集的优化技术，其核心思想是在执行合并操作时总是将较小的树作为子树添加到较大的树上。这里的'秩'通常指的是树的大小或高度。按秩合并可以有效控制并查集中树的高度，避免形成过深的树结构，从而维持合并和查找操作的效率。最终，这种方法可以保持合并后的树高度尽可能低，减少查找路径长度，提高查找效率。
在题目中，情侣的编号是成对出现的，例如(0,1), (2,3), (4,5)等。使用除以2的操作是为了将每两个连续的编号映射到同一个值上，从而识别出它们是一对情侣。例如，0和1除以2的结果都是0，2和3除以2的结果都是1，这样就可以将每对情侣映射到一个集合标识符上。这种映射确保了在并查集中，每对情侣都被认为是同一个集合的两个成员，从而可以通过并查集的合并操作确保它们在同一个集合中。
在并查集的实现中，将`self.size[fy] = None`和`self.size[fx] = None`确实是有误的。这两个操作破坏了`size`数组的完整性，使得后续使用`size`数组可能会遇到问题。正确的操作应该是在合并两个集合时只更新被合并的集合的大小，而不是设置为`None`。例如，如果将集合y合并到集合x，则应该更新`self.size[fx] += self.size[fy]`，并保留`self.size[fy]`的值不变或将其设置为0（如果不再需要使用）。这样可以保持`size`数组的正确性和有用性。