> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/union-find/765-couples-holding-hands.md).

# 765     Couples Holding Hands

## 765. [Couples Holding Hands](https://leetcode.com/problems/couples-holding-hands/description/)

## 1. Question

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. Aswapconsists 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:**

1. `len(row)`is even and in the range of`[4, 60]`.
2. `row`is guaranteed to be a permutation of`0...len(row)-1`.

## 2. Implementation

思路:

(1) 利用pos数组，记录row\[i]在row的位置

(2) 对于每对couple，我们可以发现它们的值除以2是一样的，比如(2, 3) 两个数除以2都为1, (6,7)两个除以2为3，我们可以根据这个判断当前的row\[i] 和 row\[i + 1]是否为couple，如果是则跳过，无需swap

(3) 如果row\[i] 和 row\[i + 1]不是couple的话，则我们要找到row\[i]的partner。如果row\[i]是偶数的话，则它的partner是奇数, 其值是 row\[i]/2 \* 2 + 1，通过pos数组我们可以知道partner的位置。类似的道理，如果row\[i]是奇数的话，它的partner是偶数，其值是row\[i]/2 \* 2

(4) 找到row\[i] partner位置后，我们需要更新pos\[row\[i+ 1]]的值为row\[i] partner的位置，然后再将row\[i + 1]和row\[partnerIndex]的值交换。注意这两步不能倒过来，否则当我们交换了row\[i + 1]和row\[partnerIndex]的值后，再更新pos\[row\[i + 1]]的值时，row\[i + 1]的值已经是row\[i]的partner，而不是原来的row\[i + 1]对应的数

```java
class Solution {
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int[] pos = new int[n];

        for (int i = 0; i < n; i++) {
            pos[row[i]] = i;
        }

        int res = 0;

        for (int i = 0; i < n; i += 2) {
            // 如果已经组成一对couple， 无需swap
            if (row[i]/2 == row[i + 1]/2) continue;

            int partnerIndex = 0;
            if (row[i] % 2 == 0) {
                partnerIndex = pos[row[i]/2 * 2 + 1];
            }
            else {
                partnerIndex = pos[row[i]/2 * 2];
            }

            // update pos array
            pos[row[i + 1]] = partnerIndex;

            // swap position of row[i + 1] and row[partnerIndex] to make couple
            swap(row, i + 1, partnerIndex);
            ++res;
        }
        return res;
    }

    public void swap(int[] row, int i, int j) {
        int temp = row[i];
        row[i] = row[j];
        row[j] = temp;
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(n)