力扣——情侣牵手

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。

人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。

返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。

示例 1:

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

示例 2:

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

该题主要难点就是找到一个位置上人ID与其相邻位置人的ID成情侣必须满足的关系是（2n-2,2n-1）。

注意到题目，2N个位置，N个情侣，如果要所有情侣都相邻，只有一种可能，即：
[0,1][2,3][4,5]......[2N - 2, 2N - 1]

由于替换一对情侣中任意一位，对总最少次数都没有影响，因此，可以用贪心的方式来进行替换。
方案如下：
检查0的右边是不是情侣，如果不是，将0号位置的情侣替换到1. 之后检查2的右边是不是情侣，是的话继续，不是的话把情侣换过来。。。直到2N-2

小技巧：
可以预处理把每个人对应的位置存起来，这样找0右边的情侣，就可以用O(1)的时间找到了。

row[]:

创建一个临时数组，将row[]中索引和对应值反转

pos[]:

代码实现：

public int minSwapsCouples(int[] row) {
        int ans = 0;
        int[] pos = new int[row.length];

        for (int i = 0; i < pos.length; i++) {
            pos[row[i]] = i;  //每个人对应的位置
        }

        for (int i = 0; i < pos.length; i += 2) {
            int pairPerson = row[i] ^0x1;  //i号位置的情侣应该是谁
            if (row[i + 1] == pairPerson) {
                continue;  //右边是情侣，直接继续处理下一个。
            }
            
            int nextPerson = row[i + 1]; //右边不是情侣，得到右边的人是谁
            int changePos = pos[pairPerson]; //得到情侣的位置在哪
            
            row[changePos] = nextPerson; //交换后，情侣位置坐上了右边的人nextPerson
            pos[nextPerson] = changePos; //交换后，右边人nextPerson的位置发生了改变，记录下来。
            ans++;
        }

        return ans;


    }
}

这题解题步骤我是看别人的，自己现在可没有那么聪明，现在刚学数据结构算法时间也就不到半个月。虽然这题不是我通过自己想出来，但我还是选择把它放在csdn上希望对一些和我一样初学算法的人有点帮助，能开拓你们视野。同时可能在以后我也经常可能将别人的解题思路和代码放到我的csdn文章里，这样既可以帮助我以后回忆也可以帮助一小部分人，一起共同进步。

这题让我学到就是1.这个人建立临时数组来储存每个人（ID）对应的位置的思想。

                              2.通过位异或运算符(^)来寻找一个人（ID）对应的情侣（ID）。