LC 765. 情侣牵手
题目描述
这是 LeetCode 上的 765. 情侣牵手 ,难度为 困难。
N 对情侣坐在连续排列的 2N 个座位上,想要牵到对方的手。 计算最少交换座位的次数,以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人,让他们站起来交换座位。
人和座位用 0 到 2N-1 的整数表示,情侣们按顺序编号,第一对是 (0, 1),第二对是 (2, 3),以此类推,最后一对是 (2N-2, 2N-1)。
这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
示例 1:1
2
3输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。
示例 2:1
2
3输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位,所有的情侣都已经可以手牵手了。
说明:
- len(row) 是偶数且数值在 [4, 60]范围内。
- 可以保证row 是序列
0...len(row)-1
的一个全排列。
并查集
首先,我们总是以「情侣对」为单位进行设想:
当有两对情侣相互坐错了位置,ta们两对之间形成了一个环。需要进行一次交换,使得每队情侣独立(相互牵手)
如果三对情侣相互坐错了位置,ta们三对之间形成了一个环,需要进行两次交换,使得每队情侣独立(相互牵手)
如果四对情侣相互坐错了位置,ta们四对之间形成了一个环,需要进行三次交换,使得每队情侣独立(相互牵手)
也就是说,如果我们有 k
对情侣形成了错误环,需要交换 k - 1
次才能让情侣牵手。
于是问题转化成 n / 2
对情侣中,有多少个这样的环。
可以直接使用「并查集」来做。
由于 0和1配对、2和3配对 … 因此互为情侣的两个编号除以 2 对应同一个数字,可直接作为它们的「情侣组」编号:
1 |
|
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$
贪心
还是以「情侣对」为单位进行分析:
由于题目保证有解,我们也可以从前往后(每两格作为一步)处理,对于某一个位置而言,如果下一个位置不是应该出现的情侣的话。
则对下一个位置进行交换。
同时为了方便我们找到某个值的下标,需要先对 row
进行预处理(可以使用哈希表或数组)。
1 |
|
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$
证明/分析
我们这样的做法本质是什么?
其实相当于,当我处理到第 k
个位置的时候,前面的 k - 1
个位置的情侣已经牵手成功了。我接下来怎么处理,能够使得总花销最低。
分两种情况讨论:
a. 现在处理第 k
个位置,使其牵手成功:
那么我要使得第 k
个位置的情侣也牵手成功,那么必然是保留第 k
个位置的情侣中其中一位,再进行修改,这样的成本是最小的(因为只需要交换一次)。
而且由于前面的情侣已经牵手成功了,因此交换的情侣必然在 k
位置的后面。
然后我们再考虑交换左边或者右边对最终结果的影响。
分两种情况来讨论:
- 与第
k
个位置的匹配的两个情侣不在同一个位置上:这时候无论交换左边还是右边,后面需要调整的「情侣对数量」都是一样。假设处理第k
个位置前需要调整的数量为n
的话,处理完第k
个位置(交换左边或是右边),需要调整的「情侣对数量」都为n - 1
。
- 与第
k
个位置的匹配的两个情侣在同一个位置上:这时候无论交换左边还是右边,后面需要调整的「情侣对数量」都是一样。假设处理第k
个位置前需要调整的数量为n
的话,处理完第k
个位置(交换左边或是右边),需要调整的「情侣对数量」都为n - 2
。
因此对于第 k
个位置而言,交换左边还是右边,并不会影响后续需要调整的「情侣对数量」。
b. 现在先不处理第 k
个位置,等到后面的情侣处理的时候「顺便」处理第 k
位置:
由于我们最终都是要所有位置的情侣牵手,而且每一个数值对应的情侣数值是唯一确定的。
因此我们这个等“后面”的位置处理,其实就是等与第 k
个位置互为情侣的位置处理(对应上图的就是我们是在等 【0 x】和【8 y】或者【0 8】这些位置被处理)。
由于被处理都是同一批的联通位置,因此和「a. 现在处理第 k
个位置」的分析结果是一样的。
不失一般性的,我们可以将这个分析推广到第一个位置,其实就已经是符合「当我处理到第 k
个位置的时候,前面的 k - 1
个位置的情侣已经牵手成功了」的定义了。
综上所述,我们只需要确保从前往后处理,并且每次处理都保留第 k
个位置的其中一位,无论保留的左边还是右边都能得到最优解。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.765
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!