🥇765. 情侣💑牵手@

🥇Hard

N对情侣坐在连续排列的 2N个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。

人和座位用 0到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是(2N-2, 2N-1)。

这些情侣的初始座位 row[i]是由最初始坐在第 i个座位上的人决定的。

示例 1:

输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。

示例 2:

输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

说明:

• len(row) 是偶数且数值在 [4, 60]范围内。
• 可以保证row是序列 0...len(row)-1的一个全排列。

题解

情人节不仅单身，还要被题虐，题还不会做，好难😭😭😭😭

一对情侣，两个座位，无需交换就可以牵手成功。

两对情侣，最少要交换一次

三对情侣，如果不能彼此牵手，只能是首尾相连的情况：

更多对情侣情况也可以像上面处理。通过举例总结，可以知道把 坐错了位置、逻辑上连在一起的情侣 拆成所有的情侣都能彼此牵手的 「最少交换次数 = 情侣对数 - 1」。

方法一：并查集

「首尾相连」这件事情可以使用并查集表示，将输入数组相邻位置的两个编号在并查集中进行合并。编写代码基于了下面的事实：

如果一对情侣恰好坐在了一起，并且坐在了成组的座位上，其中一个下标一定是偶数，另一个一定是奇数，并且「偶数的值 + 1 = 奇数的值」。例如编号数对 [2, 3]、[9, 8]，这些数对的特点是除以 2（下取整）得到的数相等。

题目要求出「最少交换次数」。假设一共有 N 对情侣，逻辑上连在了一起的情侣（包括坐错位置和坐对位置的情况）分别有 对，这里 n 是并查集里连通分量的个数，并且 。把逻辑上连在一起的情侣拆开，每一个连通分量至少须要 次。