LeetCode 765情侣牵手问题：用并查集/贪心算法解决座位交换（附Java/Python代码）

LeetCode 765情侣牵手问题并查集与贪心算法的双视角解析想象你走进一场算法竞赛的现场眼前的大屏幕上闪烁着这样一道题目N对情侣坐在2N个座位上如何用最少的交换次数让每对情侣都能牵到对方的手这看似浪漫的场景背后隐藏着精妙的算法设计思想。今天我们就从并查集和贪心算法两个角度深入剖析这道LeetCode 765题的解题思路。1. 问题本质与数学建模这道题的核心在于理解座位排列的数学本质。当我们将每对情侣视为一个节点时座位排列实际上构成了一个关系图。例如对于输入row [0,2,1,3]座位0和1坐着0和2情侣0和1座位2和3坐着1和3情侣0和1这形成了一个循环依赖情侣0想与伴侣坐在一起但伴侣却被情侣1占据而情侣1的伴侣又被情侣0占据。这种循环关系正是算法需要解决的关键。关键观察点每对情侣的ID具有特定关系情侣i由(2i, 2i1)组成每次交换可以解决多个不匹配关键在于识别关系图中的环提示将每个座位对视为图中的边连接两个情侣组这样问题就转化为计算图中的环数量2. 并查集解决方案并查集(Disjoint Set Union)是解决连通性问题的利器。在这个问题中我们可以将每对情侣视为一个集合通过合并操作来跟踪座位安排形成的连通分量。2.1 并查集实现细节Java实现的核心代码结构class Solution { int[] parent new int[30]; // 情侣对数不会超过30对 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void union(int a, int b) { parent[find(a)] find(b); } public int minSwapsCouples(int[] row) { int n row.length / 2; for (int i 0; i n; i) parent[i] i; for (int i 0; i row.length; i 2) { union(row[i]/2, row[i1]/2); } int cycles 0; for (int i 0; i n; i) { if (find(i) i) cycles; } return n - cycles; } }2.2 复杂度分析操作时间复杂度空间复杂度初始化O(N)O(N)合并操作O(Nα(N))-查找环O(N)-总计O(Nα(N))O(N)其中α(N)是反阿克曼函数在实际应用中可视为常数。3. 贪心算法解决方案贪心算法采取局部最优策略逐步构建全局最优解。在这个问题中我们可以从左到右处理每个座位对确保每次交换都能立即解决一对情侣的匹配问题。3.1 贪心算法实现Python实现示例class Solution: def minSwapsCouples(self, row): pos {val: idx for idx, val in enumerate(row)} swaps 0 for i in range(0, len(row), 2): partner row[i] ^ 1 # 使用异或运算快速找到伴侣 if row[i1] ! partner: # 交换伴侣到i1位置 partner_idx pos[partner] row[i1], row[partner_idx] row[partner_idx], row[i1] pos[row[partner_idx]] partner_idx pos[row[i1]] i1 swaps 1 return swaps3.2 贪心选择的正确性证明贪心算法的有效性基于以下观察局部最优性每次交换至少解决一对情侣的匹配问题无后效性当前决策不会影响后续决策的最优性完全性通过有限次交换可以到达全局最优关键证明点在于任何不立即解决当前不匹配的交换策略都不会比贪心策略更优。这是因为延迟解决当前不匹配只会将问题后移每次交换的成本固定为1因此尽早解决问题不会增加总成本4. 两种算法的对比与实践选择在实际应用中两种算法各有优劣特性并查集贪心算法时间复杂度O(Nα(N))O(N)空间复杂度O(N)O(N)代码复杂度中等较低适用场景需要分析连通分量需要具体交换步骤扩展性适合复杂关系分析适合具体操作实现选择建议面试中优先实现贪心算法代码更简洁需要分析关系结构时使用并查集竞赛中根据问题变体灵活选择5. 常见错误与调试技巧在实现过程中开发者常遇到以下问题并查集初始化错误忘记初始化父指针错误估计情侣对的数量贪心算法伴侣计算错误错误计算伴侣ID应用x ^ 1而非条件判断更新位置映射时出错边界条件处理处理空输入或单对情侣情况处理已经有序的情况调试时可以使用的测试用例test_cases [ ([0,2,1,3], 1), # 基础案例 ([3,2,0,1], 0), # 已有序 ([0,1,2,3], 0), # 理想排列 ([1,0,3,2], 0), # 相邻交换 ([5,4,3,2,1,0], 3) # 多环情况 ]在解决这类问题时最重要的是先理解问题背后的图论模型然后选择合适的数据结构来实现。无论是并查集还是贪心算法都体现了将实际问题抽象为计算模型的核心思想。