# [LeetCode] 765. Couples Holding Hands 情侣牵手

2021年09月15日 阅读数：2

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.html

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)`.java

The couples' initial seating is given by `row[i]` being the value of the person who is initially sitting in the i-th seat.python

Example 1:app

```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:ide

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

Note:post

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`.

Java: 1blog

```public int minSwapsCouples(int[] row) {
int res = 0, N = row.length;

int[] ptn = new int[N];
int[] pos = new int[N];

for (int i = 0; i < N; i++) {
ptn[i] = (i % 2 == 0 ? i + 1 : i - 1);
pos[row[i]] = i;
}

for (int i = 0; i < N; i++) {
for (int j = ptn[pos[ptn[row[i]]]]; i != j; j = ptn[pos[ptn[row[i]]]]) {
swap(row, i, j);
swap(pos, row[i], row[j]);
res++;
}
}

return res;
}

private void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}```

Java: 2

```class Solution {
private class UF {
private int[] parents;
public int count;
UF(int n) {
parents = new int[n];
for (int i = 0; i < n; i++) {
parents[i] = i;
}
count = n;
}

private int find(int i) {
if (parents[i] == i) {
return i;
}
parents[i] = find(parents[i]);
return parents[i];
}

public void union(int i, int j) {
int a = find(i);
int b = find(j);
if (a != b) {
parents[a] = b;
count--;
}
}
}
public int minSwapsCouples(int[] row) {
int N = row.length/ 2;
UF uf = new UF(N);
for (int i = 0; i < N; i++) {
int a = row[2*i];
int b = row[2*i + 1];
uf.union(a/2, b/2);
}
return N - uf.count;
}
}　```

Python:

```# Time:  O(n)
# Space: O(n)

class Solution(object):
def minSwapsCouples(self, row):
"""
:type row: List[int]
:rtype: int
"""
N = len(row)//2
couples = [[] for _ in xrange(N)]
for seat, num in enumerate(row):
couples[num//2].append(seat//2)
adj = [[] for _ in xrange(N)]
for couch1, couch2 in couples:

result = 0
for couch in xrange(N):
while couch2 != couch:
result += 1
return result  # also equals to N - (# of cycles)　　```

C++:

```int minSwapsCouples(vector<int>& row) {
int res = 0, N = row.size();

vector<int> ptn(N, 0);
vector<int> pos(N, 0);

for (int i = 0; i < N; i++) {
ptn[i] = (i % 2 == 0 ? i + 1 : i - 1);
pos[row[i]] = i;
}

for (int i = 0; i < N; i++) {
for (int j = ptn[pos[ptn[row[i]]]]; i != j; j = ptn[pos[ptn[row[i]]]]) {
swap(row[i], row[j]);
swap(pos[row[i]], pos[row[j]]);
res++;
}
}

return res;
}
```