[LeetCode] 765. Couples Holding Hands

There are n couples sitting in 2n seats arranged in a row and want to hold hands.

The people and seats are represented by an integer array row where row[i] is the ID of the person sitting in the ith seat. The couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2n - 2, 2n - 1).

Return the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

Example 1:
Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:
Input: row = [3,2,0,1]
Output: 0
Explanation: All couples are already seated side by side.

Constraints:
2n == row.length
2 <= n <= 30
n is even.
0 <= row[i] < 2n
All the elements of row are unique.

情侣牵手。

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。
人和座位用 0 到 2N - 1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N - 2, 2N - 1)。
这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/couples-holding-hands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这个题有两种思路，一种是贪心，一种是并查集 union find。我这里先给出贪心的思路。同时建议可以先做一下41题，思路类似。

这个题贪心的做法跟桶排序类似，还是试着将每个坐标上放应该放的数字。过一下第一个例子，[0, 2, 1, 3]。第一个数字是0，那么第二个数字的判断就是看他是否是第一个数字0的配偶。判断配偶的方式是看当前这个nums[i + 1]是不是等于nums[i] ^ 1。这一点不容易想到。因为配偶的座位排序要求不是非常严格，比如0和1，既可以01这样坐，也可以10这样坐。但是位运算的这个特点就可以无视0和1的顺序，来判断两个相邻的数字是否互为配偶。如果想不到这个位运算的办法，那么就只能通过先判断当前index上数字的奇偶性来判断index + 1那个位置上的数字是否是配偶。贪心的做法为什么对呢？我这里引用一个discussion给的例子，并且稍加解释。

The proof is easy. Consider a simple example: 7 1 4 6 2 3 0 5. At first step we have two choice to match the first couple: swap 7 with 0, or swap 1 with 6. Then we get 0 1 4 6 2 3 7 5 or 7 6 4 1 2 3 0 5. Pay attention that the first couple doesn’t count any more. For the later part it is composed of 4 X 2 3 Y 5 (X=6 Y=7 or X=1 Y=0). Since different couples are unrelated, we don’t care X Y is 6 7 pair or 0 1 pair. They are equivalent! Thus it means our choice doesn’t count.
Therefore, just follow the distinction and you will get it right!

具体实现的时候，这里我需要一个idx数组，记录一开始每个数字的下标是多少，因为之后 input 数组会被修改所以需要把一开始的状态记录下来。

接着开始遍历，每次走两格，因为题目规定一定是比如[0, 1], [2, 3], [4, 5]这种组合坐在一起，所以情侣之间应该满足一个是奇数一个是偶数且奇数是较大的那一个。知道这个规则之后，对于每一个我们遇到的数字，我们去 row 里找他配对的数字 next 在哪里，如果 next 正好在下一个 index i + 1那么就已经是配对好了的，反之就要找到这个数字并放到 index i + 1 这个位置上。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
	public int minSwapsCouples(int[] row) {
		int n = row.length;
		int count = 0;
		int[] idx = new int[n];
		// 记录每个数字当前的下标
		for (int i = 0; i < n; i++) {
			idx[row[i]] = i;
		}

		int next = 0;
		for (int i = 0; i < n; i += 2) {
			// 每两个作为一对，它们必然是紧邻的奇偶数，且偶数更小，故可推出另一个
			// 0 - 当前是偶数，那么配对是奇数
			// 1 - 当前是奇数，那么配对是偶数
			// next是配对数字在idx数组中的下标
			next = (row[i] & 1) == 0 ? row[i] + 1 : row[i] - 1;
			// 如果row[i],row[i+1]已然是一对，就跳过
			if (next == row[i + 1]) {
				continue;
			}

			// 反之，进行交换，使row[i+1]能和row[i]为一对
			// 即将当前row[i+1]的值放到next所在下标去，注意交换顺序
			int nextIdx = idx[next]; // 配对数字的下标
			idx[row[i + 1]] = nextIdx; // 把配对数字的下标放到i + 1这个位置上
			row[nextIdx] = row[i + 1];
			count++;
		}
		return count;
	}
}