Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
765. Couples Holding Hands.go
765. Couples Holding Hands_test.go
README.md

README.md

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.

题目大意

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()。扫完以后就可以得到最后的答案。

  • 回过头来看这道题,为什么我们从数组开头往后依次调整每一对情侣,这样交换的次数是最少的呢?其实这个方法的思想是贪心思想。从头开始往后一对一对的调整,就是可以最终做到次数最少。(具体证明笔者不会)交换到最后,最后一对情侣一定是正确的,无须交换。(因为前面每一对都调整完了,最后一对一定是正确的)

You can’t perform that action at this time.