# 765.情侣牵手

## 问题描述
[765. 情侣牵手 (Hard)](https://leetcode.cn/problems/couples-holding-hands/)

`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
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

```

**提示:**

- `2n == row.length`
- `2 <= n <= 30`
- `n` 是偶数
- `0 <= row[i] < 2n`
- `row` 中所有元素均 **无重复**

## 解题思路
我们只需要遍历`i = 0, 2, 4, 6, ...`，如果`row[i]`为偶数，就把`row[i] + 1`换到`row[i + 1]`的位置；如果`row[i]`为奇数，就把`row[i] - 1`换到`row[i + 1]`的位置，利用一个`row[i]`为`key`，`i`为`value`的哈希表和原数组来模拟这个过程。

## 代码
```cpp
class Solution {
  public:
    int minSwapsCouples(vector<int> &row) {
        std::unordered_map<int, int> ump; // row[i]为键，i为值
        for (int i = 0; i < row.size(); i++) {
            ump[row[i]] = i;
        }
        int cnt = 0;
        for (int i = 0; i < row.size(); i += 2) {
            // 应该还是要遍历row才对
            if (row[i] % 2 == 0) { // 偶数
                if (row[i + 1] != row[i] + 1) {
                    cnt++;
                    int tmp = ump[row[i] + 1]; // 原先的位置
                    int tmp_per = row[i + 1];  // i + 1座位上原先那个人的id
                    // 交换了row
                    row[i + 1] = row[i] + 1;
                    row[tmp] = tmp_per;
                    // 交换ump
                    ump[row[i] + 1] = i + 1;
                    ump[tmp_per] = tmp;
                }
            } else {
                if (row[i + 1] != row[i] - 1) {
                    cnt++;
                    int tmp = ump[row[i] - 1]; // 原先的位置
                    int tmp_per = row[i + 1];  // i + 1座位上原先那个人的id
                    // 交换了row
                    row[i + 1] = row[i] - 1;
                    row[tmp] = tmp_per;
                    // 交换ump
                    ump[row[i] - 1] = i + 1;
                    ump[tmp_per] = tmp;
                }
            }
        }
        return cnt;
    }
};
```