# 765. Couples Holding Hands

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:

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

[3   1   4   0   2   5]

[3   2   4   0   1   5]

[3   2   4   5   1   0]

``````class Solution {
public:
int minSwapsCouples(vector<int>& row) {
int res = 0, n = row.size();
for (int i = 0; i < n; i += 2) {
if (row[i + 1] == (row[i] ^ 1)) continue;
++res;
for (int j = i + 1; j < n; ++j) {
if (row[j] == (row[i] ^ 1)) {
row[j] = row[i + 1];
row[i + 1] = row[i] ^ 1;
break;
}
}
}
return res;
}
};
``````

[3   1   4   0   2   5]

``````class Solution {
public:
int minSwapsCouples(vector<int>& row) {
int res = 0, n = row.size();
vector<int> root(n, 0);
for (int i = 0; i < n; ++i) root[i] = i;
for (int i = 0; i < n; i += 2) {
int x = find(root, row[i] / 2);
int y = find(root, row[i + 1] / 2);
if (x != y) {
root[x] = y;
++res;
}
}
return res;
}
int find(vector<int>& root, int i) {
return (i == root[i]) ? i : find(root, root[i]);
}
};
``````

``````class Solution {
public:
int minSwapsCouples(vector<int>& row) {
unordered_map<int, int> m;
for (int i = 0; i < row.size(); i += 2) {
helper(m, row[i] / 2, row[i + 1] / 2);
}
return m.size();
}
void helper(unordered_map<int, int>& m, int x, int y) {
int c1 = min(x, y), c2 = max(x, y);
if (c1 == c2) return;
if (m.count(c1)) helper(m, m[c1], c2);
else m[c1] = c2;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/765

Missing Number

First Missing Positive

https://leetcode.com/problems/couples-holding-hands/

https://leetcode.com/problems/couples-holding-hands/discuss/113353/Monster-Style-C++-O(n)-unordered_map

https://leetcode.com/problems/couples-holding-hands/discuss/117520/Java-union-find-easy-to-understand-5-ms

https://leetcode.com/problems/couples-holding-hands/discuss/113362/JavaC++-O(N)-solution-using-cyclic-swapping

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation