N couples sit in 2N seats arranged in a row and want to hold hands. We want to know 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.
The people and seats are represented by an integer from 0 to 2N-1, 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).
The couples' initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.
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.
Note:
-
len(row)is even and in the range of[4, 60]. -
rowis guaranteed to be a permutation of0...len(row)-1.
情侣牵手。
题意是给偶数个人，以数组表示。他们的下标是从0到2N - 1。其中（2N - 2, 2N - 1）是情侣。现在请你做swap操作，请问至少需要swap多少次，可以让所有情侣牵手。
这个题有两种思路，一种是贪心，一种是并查集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!
首先，input是[7 1 4 6 2 3 0 5]。然后第一次swap可以swap7和0，或者swap1和6。第一次swap完了之后，数组长这样，
4 X 2 3 Y 5 (X=6 Y=7 or X=1 Y=0)
后面的swap只跟XY有关，跟已经被swap好的第一组数字无关了。所以也就无所谓先swap哪些数字了。
时间O(n)
空间O(n)
Java实现
1 class Solution {
2 public int minSwapsCouples(int[] row) {
3 int count = 0;
4 int[] pos = new int[row.length];
5 for (int i = 0; i < pos.length; i++) {
6 pos[row[i]] = i; //每个人对应的位置
7 }
8
9 for (int i = 0; i < pos.length; i += 2) {
10 // i号位置的情侣应该是谁
11 int pairPerson = (row[i] & 1) == 1 ? row[i] - 1 : row[i] + 1;
12 // 右边是情侣，直接继续处理下一个。
13 if (row[i + 1] == pairPerson) {
14 continue;
15 }
16 int nextPerson = row[i + 1]; // 右边不是情侣，得到右边的人是谁
17 int changePos = pos[pairPerson]; // 得到情侣的位置在哪
18 row[changePos] = nextPerson; // 交换后，情侣位置坐上了右边的人nextPerson
19 pos[nextPerson] = changePos; // 交换后，右边人nextPerson的位置发生了改变，记录下来。
20 count++;
21 }
22 return count;
23 }
24 }
相关题目