题目描述
这是 LeetCode 上的765. 情侣牵手，难度为 Hard。
NNN 对情侣坐在连续排列的 2N2N2N 个座位上，想要牵到对方的手。
计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。
一次交换可选择任意两人，让他们站起来交换座位。
人和座位用 000 到 2N−12N-12N−1 的整数表示，情侣们按顺序编号，第一对是 (0,1)(0, 1)(0,1)，第二对是 (2,3)(2, 3)(2,3)，以此类推，最后一对是 (2N−2,2N−1)(2N-2, 2N-1)(2N−2,2N−1)。
这些情侣的初始座位 row[i]row[i]row[i] 是由最初始坐在第 iii 个座位上的人决定的。
示例 1:
输入: row = [0, 2, 1, 3] 输出: 1 解释: 我们只需要交换row[1]和row[2]的位置即可。 复制代码
示例 2:
输入: row = [3, 2, 0, 1] 输出: 0 解释: 无需交换座位，所有的情侣都已经可以手牵手了。 复制代码
说明:
- len(row)len(row)len(row) 是偶数且数值在 [4,60][4, 60][4,60] 范围内。
- 可以保证 row 是序列 0...len(row)−10...len(row)-10...len(row)−1 的一个全排列。
并查集
首先，我们总是以「情侣对」为单位进行设想：
- 当有两对情侣相互坐错了位置，ta们两对之间形成了一个环。需要进行一次交换，使得每对情侣独立（相互牵手）
- 如果三对情侣相互坐错了位置，ta们三对之间形成了一个环，需要进行两次交换，使得每对情侣独立（相互牵手）
- 如果四对情侣相互坐错了位置，ta们四对之间形成了一个环，需要进行三次交换，使得每对情侣独立（相互牵手）
也就是说，如果我们有 kkk 对情侣形成了错误环，需要交换 k−1k - 1k−1 次才能让情侣牵手。
于是问题转化成 n/2n / 2n/2 对情侣中，有多少个这样的环。
可以直接使用「并查集」来做。
由于 0和1配对、2和3配对 ... 因此互为情侣的两个编号除以 2 对应同一个数字，可直接作为它们的「情侣组」编号。
代码：
class Solution { int[] p = new int[70]; void union(int a, int b) { p[find(a)] = p[find(b)]; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } public int minSwapsCouples(int[] row) { int n = row.length, m = n / 2; for (int i = 0; i < m; i++) p[i] = i; for (int i = 0; i < n; i += 2) { union(row[i] / 2, row[i + 1] / 2); } int cnt = 0; for (int i = 0; i < m; i++) { if (i == find(i)) cnt++; } return m - cnt; } } 复制代码
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(n)O(n)O(n)
贪心算法
还是以「情侣对」为单位进行分析：
由于题目保证有解，我们也可以从前往后（每两格作为一步）处理，对于某一个位置而言，如果下一个位置不是应该出现的情侣的话。
则对下一个位置进行交换。
同时为了方便我们找到某个值的下标，需要先对 rowrowrow 进行预处理（可以使用哈希表或数组）。
代码：
class Solution { public int minSwapsCouples(int[] row) { int n = row.length; int ans = 0; int[] cache = new int[n]; for (int i = 0; i < n; i++) cache[row[i]] = i; for (int i = 0; i < n - 1; i += 2) { int a = row[i], b = a ^ 1; if (row[i + 1] != b) { int src = i + 1, tar = cache[b]; cache[row[tar]] = src; cache[row[src]] = tar; swap(row, src, tar); ans++; } } return ans; } void swap(int[] nums, int a, int b) { int c = nums[a]; nums[a] = nums[b]; nums[b] = c; } } 复制代码
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(n)O(n)O(n)
证明
我们这样的做法本质是什么？
其实相当于，当我处理到第 k 个位置的时候，前面的 k - 1 个位置的情侣已经牵手成功了。我接下来怎么处理，能够使得总花销最低。
分两种情况讨论：
a. 现在处理第 k 个位置，使其牵手成功：
那么我要使得第 k 个位置的情侣也牵手成功，那么必然是保留第 k 个位置的情侣中其中一位，再进行修改，这样的成本是最小的（因为只需要交换一次）。
而且由于前面的情侣已经牵手成功了，因此交换的情侣必然在 k 位置的后面。
然后我们再考虑交换左边或者右边对最终结果的影响。
分两种情况来讨论：
- 与第
k个位置的匹配的两个情侣不在同一个位置上：这时候无论交换左边还是右边，后面需要调整的「情侣对数量」都是一样。假设处理第k个位置前需要调整的数量为n的话，处理完第k个位置（交换左边或是右边），需要调整的「情侣对数量」都为n - 1。
- 与第
k个位置的匹配的两个情侣在同一个位置上：这时候无论交换左边还是右边，后面需要调整的「情侣对数量」都是一样。假设处理第k个位置前需要调整的数量为n的话，处理完第k个位置（交换左边或是右边），需要调整的「情侣对数量」都为n - 2。
因此对于第 k 个位置而言，交换左边还是右边，并不会影响后续需要调整的「情侣对数量」。
b. 现在先不处理第 k 个位置，等到后面的情侣处理的时候「顺便」处理第 k 位置：
由于我们最终都是要所有位置的情侣牵手，而且每一个数值对应的情侣数值是唯一确定的。
因此我们这个等“后面”的位置处理，其实就是等与第 k 个位置互为情侣的位置处理（对应上图的就是我们是在等 【0 x】和【8 y】或者【0 8】这些位置被处理）。
由于被处理都是同一批的联通位置，因此和「a. 现在处理第 k 个位置」的分析结果是一样的。
不失一般性的，我们可以将这个分析推广到第一个位置，其实就已经是符合「当我处理到第 k 个位置的时候，前面的 k - 1 个位置的情侣已经牵手成功了」的定义了。
综上所述，我们只需要确保从前往后处理，并且每次处理都保留第 k 个位置的其中一位，无论保留的左边还是右边都能得到最优解。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.765 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
