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:

len(row) is even and in the range of [4, 60].
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 个座位上的人决定的。

说明:

len(row) 是偶数且数值在 [4, 60]范围内。
可以保证 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()。扫完以后就可以得到最后的答案。
回过头来看这道题，为什么我们从数组开头往后依次调整每一对情侣，这样交换的次数是最少的呢？其实这个方法的思想是贪心思想。从头开始往后一对一对的调整，就是可以最终做到次数最少。(具体证明笔者不会)交换到最后，最后一对情侣一定是正确的，无须交换。(因为前面每一对都调整完了，最后一对一定是正确的)

代码 #


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()
}

⬅️上一页

下一页➡️