mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-08 10:24:58 +08:00
64 lines
3.9 KiB
Markdown
Executable File
64 lines
3.9 KiB
Markdown
Executable File
# [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()`。扫完以后就可以得到最后的答案。
|
||
- 回过头来看这道题，为什么我们从数组开头往后依次调整每一对情侣，这样交换的次数是最少的呢？其实这个方法的思想是贪心思想。从头开始往后一对一对的调整，就是可以最终做到次数最少。(具体证明笔者不会)交换到最后，最后一对情侣一定是正确的，无须交换。(因为前面每一对都调整完了，最后一对一定是正确的)
|