并查集解决情侣牵手问题：算法与实现-北京尧图网络

1. 问题背景与核心挑战力扣765题情侣牵手描述了一个有趣的情境N对情侣随机坐在一排2N个座位上现在需要通过最少的交换操作让每对情侣都能相邻而坐。这道题看似是排列组合问题实则考察对并查集(Union-Find)这一经典数据结构的理解和灵活运用。我第一次遇到这个问题时尝试用贪心算法逐个位置处理很快发现会陷入局部最优的困境。后来观察到每对情侣(2i, 2i1)的座位关系实际上构成了连通性问题这正是并查集的用武之地。并查集能够高效管理元素的分组关系特别适合处理这类动态连通性场景。2. 并查集数据结构精要2.1 基础概念与实现并查集维护一组不相交的动态集合主要支持三种操作MakeSet(x): 创建仅含x的新集合Union(x,y): 合并包含x和y的集合Find(x): 查找x所在集合的代表元素典型实现使用数组parent记录每个元素的父节点通过路径压缩和按秩合并两种优化策略可以将操作时间复杂度降至接近常数级别。class UnionFind: def __init__(self, size): self.parent list(range(size)) self.rank [0] * size 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): x_root self.find(x) y_root self.find(y) if x_root y_root: return # 按秩合并 if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root else: self.parent[y_root] x_root if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 12.2 在本题中的特殊应用情侣牵手问题需要将座位视为节点将需要交换的关系视为边。具体来说将每对情侣(2i, 2i1)视为一个逻辑节点对于座位上的两个人如果他们不是情侣就需要建立连通关系最终答案等于所有连通分量的大小减一的总和这种建模方式巧妙地将座位交换问题转化为连通分量计数问题。例如假设有三对情侣形成环状错位只需要两次交换即可解决对应连通分量大小为3需要3-12次操作。3. 问题求解的完整实现3.1 算法步骤详解初始化并查集大小为情侣对数N遍历座位每次处理两个相邻位置计算两人对应的情侣组编号x row[i]//2如果两人不是同一组(x ! y)合并两组统计所有连通分量累加(size-1)得到答案3.2 Python实现代码def minSwapsCouples(row): n len(row) // 2 uf UnionFind(n) for i in range(0, len(row), 2): x row[i] // 2 y row[i1] // 2 if x ! y: uf.union(x, y) # 统计各连通分量大小 count {} for i in range(n): root uf.find(i) count[root] count.get(root, 0) 1 return sum(v-1 for v in count.values())3.3 复杂度分析时间复杂度O(Nα(N))其中α是反阿克曼函数实际应用中可视为常数空间复杂度O(N)用于存储父节点和秩数组4. 关键问题与优化技巧4.1 为什么连通分量大小减一等于交换次数每个连通分量形成一棵树要将树中所有节点正确配对需要的最少交换次数等于边数即节点数减一。例如分量大小2需要1次交换分量大小3需要2次交换形成环再2次解开4.2 实际编码中的常见错误忘记处理相邻座位已经是情侣的情况错误计算情侣组编号应使用整数除法//2并查集实现时未进行路径压缩导致超时最后统计连通分量时重复计算提示可以在合并操作时直接统计交换次数避免最后的额外遍历。当两个不同集合合并时交换次数1。4.3 替代解法比较贪心算法虽然也能解决问题但时间复杂度升至O(N^2)代码实现更复杂需要维护当前位置的配对状态不如并查集解法直观和高效5. 并查集的扩展应用场景并查集在算法竞赛和工程实践中应用广泛典型场景包括图的连通分量计算动态连通性问题等价关系处理图像处理中的像素连通区域社交网络中的好友关系维护理解并查集在情侣牵手问题中的应用可以帮助我们培养将具体问题抽象为连通性问题的思维能力。这种建模技巧在解决许多复杂问题时都非常有效。

并查集解决情侣牵手问题：算法与实现

相关推荐

GLM4源码包部署实战：从解压配置到OpenAI兼容服务

模拟CMOS平方律曲线全链路：Cox、工作区、gm与ro

Oracle迁移KingbaseES实战指南与优化策略

更多资讯

Python基础：第 10 篇 · for 循环与 range：遍历的正确姿势

Python基础：第 09 篇 · while 循环：重复直到不满足

自动化测试学习全攻略：从零到精通

急热急冷热流道：省下多少成本，提多少良率

华为校招机考真题 AI方向 2026-10-23 选择题【真题及答案解析】

一键完整导出微信聊天记录：留痕 WeChatMsg

今日更新

GUI自动化测试中的ScreenLayout：从硬编码坐标到声明式画面地图

LLC谐振变换器12V25A 300W开关电源设计与调试全攻略

ESP32多应用Flash数据隔离：分区表与NVS namespace实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？