# [765. Couples Holding Hands](https://leetcode.com/problems/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`.


## 题目大意

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。

说明:

1. len(row) 是偶数且数值在 [4, 60]范围内。  
2. 可以保证 row 是序列 0...len(row)-1 的一个全排列。  


## 解题思路

- 给出一个数组，数组里面两两相邻的元素代表一对情侣。情侣编号是从 0 开始的：0 和 1 是情侣，2 和 3 是情侣……这些情侣坐在一排，但是并非成对坐着一起的，问如何用最小的次数交换座位以后，情侣能两两坐在一起。
- 这道题的突破口是如何找到最小的交换次数。乍一想可能没有思路。直觉告诉我们，这种难题，很可能最后推出来的结论，或者公式是一个很简单的式子。(事实此题确实是这种情况)先不考虑最小交换次数，用正常的方法来处理这道题。举个例子：【3 1 4 0 2 5】，从数组 0 下标开始往后扫。

        初始状态
        
        集合 0：0，1
        集合 1：2，3
        集合 2：4，5

    3 和 1 不是情侣，将 3 和 1 所在集合 `union()` 起来。3 所在集合是 1 ，1 所在集合是 0，将 0 和 1 号集合 `union()` 起来。因为情侣 0 和情侣 1 是集合 0 ，情侣 2 和情侣 3 是集合 1，以此类推。

        集合 0 和 1：0，1，2，3
        集合 2：4，5

- 继续往后扫，4 和 0 不在同一个集合，4 在集合 3，0 在集合 0，那么把它们 `union()` 起来。

        集合 0 和 1 和 2：0，1，2，3，4，5

    在上面集合合并的过程中，合并了 2 次。那么就代表最少需要交换 2 次。也可以通过 `len(row)/2 - uf.count` 来计算。`len(row)/2` 是初始集合总数，`uf.count` 是最后剩下的集合数，两者相减就是中间交换的次数。

- 最后实现的代码非常简单。并查集先相邻的两两元素 `union()` 在一起。然后扫原数组，每次扫相邻的两个，通过这两个元素值所在集合，进行 `union()`。扫完以后就可以得到最后的答案。
- 回过头来看这道题，为什么我们从数组开头往后依次调整每一对情侣，这样交换的次数是最少的呢？其实这个方法的思想是贪心思想。从头开始往后一对一对的调整，就是可以最终做到次数最少。(具体证明笔者不会)交换到最后，最后一对情侣一定是正确的，无须交换。(因为前面每一对都调整完了，最后一对一定是正确的)


## 代码

```go

package leetcode

import (
	"github.com/halfrost/LeetCode-Go/template"
)

func minSwapsCouples(row []int) int {
	if len(row)&1 == 1 {
		return 0
	}
	uf := template.UnionFind{}
	uf.Init(len(row))
	for i := 0; i < len(row)-1; i = i + 2 {
		uf.Union(i, i+1)
	}
	for i := 0; i < len(row)-1; i = i + 2 {
		if uf.Find(row[i]) != uf.Find(row[i+1]) {
			uf.Union(row[i], row[i+1])
		}
	}
	return len(row)/2 - uf.TotalCount()
}

```


----------------------------------------------
<div style="display: flex;justify-content: space-between;align-items: center;">
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0700~0799/0763.Partition-Labels/">⬅️上一页</a></p>
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0700~0799/0766.Toeplitz-Matrix/">下一页➡️</a></p>
</div>
