Leetcode 【765. 情侣牵手】

本文主要是介绍Leetcode 【765. 情侣牵手】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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.length
• 2 <= n <= 30
• n 是偶数
• 0 <= row[i] < 2n
• row 中所有元素均无重复

方法一：贪心

class Solution:def minSwapsCouples(self, row: List[int]) -> int:wrong_couple,n=0,len(row)//2couple={}for i in range(n):couple[2*i]=2*i+1couple[2*i+1]=2*ifor i in range(n):if row[2*i]!=couple[row[2*i+1]]:for j in range(2*n):if row[j]==couple[row[2*i+1]]:row[2*i],row[j]=row[j],row[2*i]wrong_couple+=1continuereturn wrong_couple

方法二：并查集

class Solution:def minSwapsCouples(self, row):def find(x):if p[x] != x:p[x] = find(p[x])return p[x]def union(a, b):p[find(a)] = p[find(b)]n, m = len(row), len(row) // 2p=[i for i in range(m)]for i in range(0, n, 2):union(row[i] // 2, row[i + 1] // 2)cnt = 0for i in range(m):if i == find(i):cnt += 1return m - cnt

并查集模板及思路：

class UnionFind:def __init__(self, n):self.parent = [i for i in range(n)]  # 初始化每个元素的父节点为自己self.rank = [0] * n  # 初始化每个集合的秩为0def 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)root_y = self.find(y)if root_x != root_y:if self.rank[root_x] < self.rank[root_y]:self.parent[root_x] = root_yelif self.rank[root_x] > self.rank[root_y]:self.parent[root_y] = root_xelse:self.parent[root_x] = root_yself.rank[root_y] += 1

• __init__方法： 构造方法初始化并查集，self.parent数组表示每个元素的父节点，self.rank数组表示每个集合的秩。

• find方法： 查找操作，通过递归找到元素的根节点，同时进行路径压缩。

• union方法： 合并操作，首先找到两个元素所在集合的根节点，然后根据秩的大小判断如何合并。如果两个根节点的秩相等，就将其中一个根节点连接到另一个根节点上，并更新秩。如果秩不相等，将秩小的根节点连接到秩大的根节点上，不需要更新秩。

这篇关于Leetcode 【765. 情侣牵手】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---