文章目录问题描述示例算法原理核心思想Python 实现代码执行流程详解示例 1row [0, 2, 1, 3]1. 初始化阶段2. 遍历座位对3. 计算结果连通分量数详解什么是连通分量情侣牵手问题中的连通分量连通分量数的作用连通分量数的计算过程连通分量数的直观理解扩展示例分析示例 2row [0, 2, 4, 1, 3, 5]1. 初始化阶段2. 遍历座位对3. 计算结果关键技术点解析1. 情侣编号转换2. 并查集核心操作3. 交换次数计算原理完整执行流程图复杂度分析总结问题描述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 解释: 无需交换座位所有的情侣都已经可以手牵手了。算法原理这个问题可以通过**并查集Union-Find**数据结构高效解决。核心思路是将每个情侣对视为一个节点通过合并操作找出连通分量进而计算最少交换次数。核心思想情侣对编号 每对情侣的 ID 除以 2 可得到统一编号如 0 和 1 的编号都是 02 和 3 的编号都是 1并查集操作 遍历座位数组将相邻座位上的情侣编号进行合并计算交换次数 最终交换次数 情侣对数 - 连通分量数量Python 实现代码from typing import List class Solution: def minSwapsCouples(self, row: List[int]) - int: 计算使所有情侣并肩而坐的最少交换次数 参数: row: 表示座位上人员 ID 的数组长度为 2n 返回: 最少交换次数 n len(row) couple_count n // 2 # 情侣对总数 # 初始化并查集 parent list(range(couple_count)) # 父节点数组 component_count couple_count # 连通分量数量 def find(u: int) - int: 查找节点的根节点带路径压缩 while parent[u] ! u: parent[u] parent[parent[u]] # 路径压缩 u parent[u] return u def union(u: int, v: int) - None: 合并两个集合 nonlocal component_count root_u find(u) root_v find(v) if root_u ! root_v: parent[root_u] root_v component_count - 1 # 遍历所有相邻座位对 for i in range(0, n, 2): # 获取当前两个座位上人员的情侣编号 couple1 row[i] // 2 couple2 row[i1] // 2 union(couple1, couple2) # 最少交换次数 情侣对数 - 连通分量数量 return couple_count - component_count执行流程详解示例 1row [0, 2, 1, 3]1. 初始化阶段n len(row) 4 couple_count n // 2 2 # 情侣对总数 parent list(range(couple_count)) [0, 1] # 父节点数组 component_count couple_count 2 # 初始连通分量数为 22. 遍历座位对第一次循环 (i0)couple1row[0]//20//20couple2row[1]//22//21union(0,1)# 合并情侣 0 和情侣 1union 函数执行过程def union(u: int, v: int)-None: nonlocal component_count root_ufind(0)→0# 0 的根是自身root_vfind(1)→1# 1 的根是自身ifroot_u!root_v:# 0 ! 1需要合并parent[root_u]root_v → parent[0]1component_count -1→ component_count1第二次循环 (i2)couple1row[2]//21//20couple2row[3]//23//21union(0,1)# 再次合并情侣 0 和情侣 1union 函数执行过程root_ufind(0)→ parent[0]1→ 最终根是1root_vfind(1)→1的根是自身ifroot_u!root_v:# 1 1不需要合并# 不执行任何操作3. 计算结果return couple_count - component_count 2 - 1 1连通分量数详解什么是连通分量连通分量 Connected Component是图论中的基本概念指的是图中相互连通但与其他部分不连通的子图。通俗解释 把每个元素看作一个节点如果两个节点之间存在连接关系在情侣牵手问题中就是坐在相邻座位上就用一条边连接它们最终形成的相互连接的节点集合就是一个连通分量情侣牵手问题中的连通分量在我们的问题中节点 每对情侣编号为 0, 1, 2, …, n-1边 如果两对情侣坐在相邻座位上就建立一条边连通分量 通过边相互连接的情侣对集合连通分量数的作用最少交换次数 情侣对数 - 连通分量数原理 每个连通分量的大小为 k 时需要 k-1 次交换总交换次数 Σ(k_i - 1) 总情侣对数 - 连通分量数证明过程假设我们有m个连通分量大小分别为k1, k2, …, km总交换次数 (k1-1) (k2-1) … (km-1)展开后 (k1 k2 … km) - m而k1 k2 … km 总情侣对数所以总交换次数 总情侣对数 - mm是连通分量数具体案例验证案例1row [0, 2, 1, 3]连通分量数 1大小k2总交换次数 2-11案例2row [3, 2, 0, 1]连通分量数 2每个大小k1总交换次数 (1-1)(1-1)0案例3row [0, 2, 4, 1, 3, 5]连通分量数 1大小k3总交换次数 3-12案例4row [0, 1, 2, 3, 4, 5]连通分量数 3每个大小k1总交换次数 3-30为什么这个公式成立本质原因 连通分量代表了一个“环”的结构每对情侣在环中都处于错误的位置每次交换可以打破一个环减少需要调整的情侣对数最终需要的交换次数恰好是环的数量连通分量数的补数直观比喻 把每个连通分量看作一个拼图每个拼图有k块碎片要拼好这个拼图需要k-1次拼接操作最终总拼接次数就是所有拼图的(k-1)之和连通分量数的计算过程# 初始化 component_count couple_count # 初始连通分量数等于情侣对数 # 合并操作 def union(u: int, v: int) - None: nonlocal component_count root_u find(u) root_v find(v) if root_u ! root_v: parent[root_u] root_v component_count - 1 # 每合并两个不同分量连通分量数减 1关键步骤 初始状态 每个情侣对都是独立的连通分量连通分量数等于情侣对数合并操作 每成功合并两个不同的连通分量连通分量数减 1最终结果 合并完成后连通分量数就是图中相互独立的子图数量连通分量数的直观理解想象一群人站在操场上每个人代表一对情侣如果两个人手拉手就表示他们坐在相邻座位上最终形成的几群手拉手的人每一群就是一个连通分量连通分量数就是这样的群体数量扩展示例分析示例 2row [0, 2, 4, 1, 3, 5]1. 初始化阶段n len(row) 6 couple_count n // 2 3 # 情侣对总数 parent list(range(couple_count)) [0, 1, 2] # 父节点数组 component_count couple_count 3 # 初始连通分量数为 32. 遍历座位对第一次循环 (i0)couple1row[0]//20//20couple2row[1]//22//21union(0,1)# 合并情侣 0 和情侣 1find(0) → 0find(1) → 1合并后 parent[0] 1component_count 3 - 1 2第二次循环 (i2)couple1 row[2] // 2 4 // 2 2 couple2 row[3] // 2 1 // 2 0 union(2, 0) # 合并情侣 2 和情侣 0find(2) → 2find(0) → parent[0] 1 → 根是 1合并后 parent[2] 1component_count 2 - 1 1第三次循环 (i4)couple1 row[4] // 2 3 // 2 1 couple2 row[5] // 2 5 // 2 2 union(1, 2) # 合并情侣 1 和情侣 2find(1) → 1find(2) → parent[2] 1 → 根是 1已经在同一个连通分量中无需合并component_count 保持 13. 计算结果最少交换次数3-12为什么最少交换次数是 2当前座位[0,2,4,1,3,5]目标座位[0,1,2,3,4,5]交换步骤1. 交换2和1→[0,1,4,2,3,5]2. 交换4和2→[0,1,2,3,4,5]总共需要2次交换关键技术点解析1. 情侣编号转换couple_id person_id // 20 和 1 → 0第一对情侣2 和 3 → 1第二对情侣4 和 5 → 2第三对情侣以此类推2. 并查集核心操作find 函数 带路径压缩的查找确保每次查询后树的高度尽可能低union 函数 按秩合并这里简化为直接合并减少树的高度3. 交换次数计算原理每个连通分量的大小为 k 时需要 k-1 次交换总交换次数 Σ(k_i - 1) 总情侣对数 - 连通分量数完整执行流程图开始 | v 初始化并查集 | v 遍历座位数组步长 2 | --- 对每对相邻座位 | | | v | 获取两人的情侣编号 | | | v | 合并两个情侣编号 | v 计算最少交换次数 情侣对数 - 连通分量数 | v 返回结果复杂度分析时间复杂度 O(n α(n))其中α是阿克曼函数的反函数几乎可以看作常数空间复杂度 O(n)用于存储并查集的父节点数组总结通过这个详细的解析我们可以清晰地看到算法如何将复杂的座位交换问题转化为连通分量的计算从而高效地得到最少交换次数。并查集数据结构在这个问题中发挥了关键作用使得我们能够在接近线性的时间复杂度内解决问题。核心要点 理解情侣编号的转换规则掌握并查集的基本操作find 和 union理解连通分量数的物理意义记住最少交换次数的计算公式情侣对数 - 连通分量数
LeetCode765.情侣牵手
发布时间：2026/5/28 3:13:09
文章目录问题描述示例算法原理核心思想Python 实现代码执行流程详解示例 1row [0, 2, 1, 3]1. 初始化阶段2. 遍历座位对3. 计算结果连通分量数详解什么是连通分量情侣牵手问题中的连通分量连通分量数的作用连通分量数的计算过程连通分量数的直观理解扩展示例分析示例 2row [0, 2, 4, 1, 3, 5]1. 初始化阶段2. 遍历座位对3. 计算结果关键技术点解析1. 情侣编号转换2. 并查集核心操作3. 交换次数计算原理完整执行流程图复杂度分析总结问题描述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 解释: 无需交换座位所有的情侣都已经可以手牵手了。算法原理这个问题可以通过**并查集Union-Find**数据结构高效解决。核心思路是将每个情侣对视为一个节点通过合并操作找出连通分量进而计算最少交换次数。核心思想情侣对编号 每对情侣的 ID 除以 2 可得到统一编号如 0 和 1 的编号都是 02 和 3 的编号都是 1并查集操作 遍历座位数组将相邻座位上的情侣编号进行合并计算交换次数 最终交换次数 情侣对数 - 连通分量数量Python 实现代码from typing import List class Solution: def minSwapsCouples(self, row: List[int]) - int: 计算使所有情侣并肩而坐的最少交换次数 参数: row: 表示座位上人员 ID 的数组长度为 2n 返回: 最少交换次数 n len(row) couple_count n // 2 # 情侣对总数 # 初始化并查集 parent list(range(couple_count)) # 父节点数组 component_count couple_count # 连通分量数量 def find(u: int) - int: 查找节点的根节点带路径压缩 while parent[u] ! u: parent[u] parent[parent[u]] # 路径压缩 u parent[u] return u def union(u: int, v: int) - None: 合并两个集合 nonlocal component_count root_u find(u) root_v find(v) if root_u ! root_v: parent[root_u] root_v component_count - 1 # 遍历所有相邻座位对 for i in range(0, n, 2): # 获取当前两个座位上人员的情侣编号 couple1 row[i] // 2 couple2 row[i1] // 2 union(couple1, couple2) # 最少交换次数 情侣对数 - 连通分量数量 return couple_count - component_count执行流程详解示例 1row [0, 2, 1, 3]1. 初始化阶段n len(row) 4 couple_count n // 2 2 # 情侣对总数 parent list(range(couple_count)) [0, 1] # 父节点数组 component_count couple_count 2 # 初始连通分量数为 22. 遍历座位对第一次循环 (i0)couple1row[0]//20//20couple2row[1]//22//21union(0,1)# 合并情侣 0 和情侣 1union 函数执行过程def union(u: int, v: int)-None: nonlocal component_count root_ufind(0)→0# 0 的根是自身root_vfind(1)→1# 1 的根是自身ifroot_u!root_v:# 0 ! 1需要合并parent[root_u]root_v → parent[0]1component_count -1→ component_count1第二次循环 (i2)couple1row[2]//21//20couple2row[3]//23//21union(0,1)# 再次合并情侣 0 和情侣 1union 函数执行过程root_ufind(0)→ parent[0]1→ 最终根是1root_vfind(1)→1的根是自身ifroot_u!root_v:# 1 1不需要合并# 不执行任何操作3. 计算结果return couple_count - component_count 2 - 1 1连通分量数详解什么是连通分量连通分量 Connected Component是图论中的基本概念指的是图中相互连通但与其他部分不连通的子图。通俗解释 把每个元素看作一个节点如果两个节点之间存在连接关系在情侣牵手问题中就是坐在相邻座位上就用一条边连接它们最终形成的相互连接的节点集合就是一个连通分量情侣牵手问题中的连通分量在我们的问题中节点 每对情侣编号为 0, 1, 2, …, n-1边 如果两对情侣坐在相邻座位上就建立一条边连通分量 通过边相互连接的情侣对集合连通分量数的作用最少交换次数 情侣对数 - 连通分量数原理 每个连通分量的大小为 k 时需要 k-1 次交换总交换次数 Σ(k_i - 1) 总情侣对数 - 连通分量数证明过程假设我们有m个连通分量大小分别为k1, k2, …, km总交换次数 (k1-1) (k2-1) … (km-1)展开后 (k1 k2 … km) - m而k1 k2 … km 总情侣对数所以总交换次数 总情侣对数 - mm是连通分量数具体案例验证案例1row [0, 2, 1, 3]连通分量数 1大小k2总交换次数 2-11案例2row [3, 2, 0, 1]连通分量数 2每个大小k1总交换次数 (1-1)(1-1)0案例3row [0, 2, 4, 1, 3, 5]连通分量数 1大小k3总交换次数 3-12案例4row [0, 1, 2, 3, 4, 5]连通分量数 3每个大小k1总交换次数 3-30为什么这个公式成立本质原因 连通分量代表了一个“环”的结构每对情侣在环中都处于错误的位置每次交换可以打破一个环减少需要调整的情侣对数最终需要的交换次数恰好是环的数量连通分量数的补数直观比喻 把每个连通分量看作一个拼图每个拼图有k块碎片要拼好这个拼图需要k-1次拼接操作最终总拼接次数就是所有拼图的(k-1)之和连通分量数的计算过程# 初始化 component_count couple_count # 初始连通分量数等于情侣对数 # 合并操作 def union(u: int, v: int) - None: nonlocal component_count root_u find(u) root_v find(v) if root_u ! root_v: parent[root_u] root_v component_count - 1 # 每合并两个不同分量连通分量数减 1关键步骤 初始状态 每个情侣对都是独立的连通分量连通分量数等于情侣对数合并操作 每成功合并两个不同的连通分量连通分量数减 1最终结果 合并完成后连通分量数就是图中相互独立的子图数量连通分量数的直观理解想象一群人站在操场上每个人代表一对情侣如果两个人手拉手就表示他们坐在相邻座位上最终形成的几群手拉手的人每一群就是一个连通分量连通分量数就是这样的群体数量扩展示例分析示例 2row [0, 2, 4, 1, 3, 5]1. 初始化阶段n len(row) 6 couple_count n // 2 3 # 情侣对总数 parent list(range(couple_count)) [0, 1, 2] # 父节点数组 component_count couple_count 3 # 初始连通分量数为 32. 遍历座位对第一次循环 (i0)couple1row[0]//20//20couple2row[1]//22//21union(0,1)# 合并情侣 0 和情侣 1find(0) → 0find(1) → 1合并后 parent[0] 1component_count 3 - 1 2第二次循环 (i2)couple1 row[2] // 2 4 // 2 2 couple2 row[3] // 2 1 // 2 0 union(2, 0) # 合并情侣 2 和情侣 0find(2) → 2find(0) → parent[0] 1 → 根是 1合并后 parent[2] 1component_count 2 - 1 1第三次循环 (i4)couple1 row[4] // 2 3 // 2 1 couple2 row[5] // 2 5 // 2 2 union(1, 2) # 合并情侣 1 和情侣 2find(1) → 1find(2) → parent[2] 1 → 根是 1已经在同一个连通分量中无需合并component_count 保持 13. 计算结果最少交换次数3-12为什么最少交换次数是 2当前座位[0,2,4,1,3,5]目标座位[0,1,2,3,4,5]交换步骤1. 交换2和1→[0,1,4,2,3,5]2. 交换4和2→[0,1,2,3,4,5]总共需要2次交换关键技术点解析1. 情侣编号转换couple_id person_id // 20 和 1 → 0第一对情侣2 和 3 → 1第二对情侣4 和 5 → 2第三对情侣以此类推2. 并查集核心操作find 函数 带路径压缩的查找确保每次查询后树的高度尽可能低union 函数 按秩合并这里简化为直接合并减少树的高度3. 交换次数计算原理每个连通分量的大小为 k 时需要 k-1 次交换总交换次数 Σ(k_i - 1) 总情侣对数 - 连通分量数完整执行流程图开始 | v 初始化并查集 | v 遍历座位数组步长 2 | --- 对每对相邻座位 | | | v | 获取两人的情侣编号 | | | v | 合并两个情侣编号 | v 计算最少交换次数 情侣对数 - 连通分量数 | v 返回结果复杂度分析时间复杂度 O(n α(n))其中α是阿克曼函数的反函数几乎可以看作常数空间复杂度 O(n)用于存储并查集的父节点数组总结通过这个详细的解析我们可以清晰地看到算法如何将复杂的座位交换问题转化为连通分量的计算从而高效地得到最少交换次数。并查集数据结构在这个问题中发挥了关键作用使得我们能够在接近线性的时间复杂度内解决问题。核心要点 理解情侣编号的转换规则掌握并查集的基本操作find 和 union理解连通分量数的物理意义记住最少交换次数的计算公式情侣对数 - 连通分量数
![[023][数据模块]深入剖析 MyBatis 通用枚举处理器：BaseEnum 与 BaseEnumTypeHandler 的设计与实现](http://pic.xiahunao.cn/yaotu/[023][数据模块]深入剖析 MyBatis 通用枚举处理器：BaseEnum 与 BaseEnumTypeHandler 的设计与实现)
