1.题目基本信息

1.1.题目描述

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。

人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n - 2, 2n - 1)。

返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。

1.2.题目地址

https://leetcode.cn/problems/couples-holding-hands/description/

2.解题方法

2.1.解题思路

并查集。以每个元素为结点，「每一对的关系」和「(偶下标,奇下标)的关系」作为边，构建图。最小的交换次数为图中每个"连通分量中结点个数//2-1"的和

3.解题代码

python3代码

class UnionFind():
    def __init__(self):
        self.roots = {}
        self.rootSizes = {}
        self.setCnt = 0

    def add(self, x):
        if x not in self.roots:
            self.roots[x] = x
            self.rootSizes[x] = 1
            self.setCnt += 1

    def find(self, x):
        root = x
        while root != self.roots[root]:
            root = self.roots[root]
        while x != root:
            tmp = self.roots[x]
            self.roots[x] = root
            x = tmp
        return root
    
    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            if self.rootSizes[rootx] < self.rootSizes[rooty]:
                self.roots[rootx] = rooty
                self.rootSizes[rooty] += self.rootSizes[rootx]
            else:
                self.roots[rooty] = rootx
                self.rootSizes[rootx] += self.rootSizes[rooty]
            self.setCnt -= 1


class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        # 思路：并查集。以每个元素为结点，「每一对的关系」和「(偶下标,奇下标)的关系」作为边，构建图。最小的交换次数为图中每个"连通分量中结点个数//2-1"的和
        n = len(row)
        uf = UnionFind()
        for i in range(0, n, 2):
            uf.add(row[i])
            uf.add(i)
            uf.add(row[i + 1])
            uf.add(i + 1)
            uf.union(row[i], row[i + 1])
            uf.union(i, i + 1)
        result = 0
        # print(uf.roots)
        # print(uf.rootSizes)
        for k, v in uf.roots.items():
            if k == v:
                result += uf.rootSizes[k] // 2 - 1
        return result

4.执行结果