0801. 使序列递增的最小交换次数
我们有两个长度相等且不为空的整型数组 A 和 B 。
我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。
在交换过一些元素之后，数组 A 和 B 都应该是严格递增的（数组严格递增的条件仅为A[0] < A[1] < A[2] < ... < A[A.length - 1]）。
给定数组 A 和 B ，请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。
示例:
输入: A = [1,3,5,4], B = [1,2,3,7]
输出: 1
解释:
交换 A[3] 和 B[3] 后，两个数组如下:
A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
两个数组均为严格递增的。
注意:
A, B 两个数组的长度总是相等的，且长度的范围为 [1, 1000]。
A[i], B[i] 均为 [0, 2000]区间内的整数。
- 动态规划
- 暂无
要想解决这道题，需要搞定两个关键点。
这其实也是可以使用动态规划解决问题的关键条件。对于这道题来说，最小的子问题就是当前项和前一项组成的局部，无法再小了，没有必要再大了。
为什么只关心两个数字即可？因为要使得整个数组递增，假设前面的 i - 2 项已经满足递增了，那么现在采取某种方式使得满足 A[i] > A[i-1] 即可(B 也是同理)。
因为 A[i - 1] > A[i-2] 已经成立，因此如果 A[i] > A[i - 1]，那么整体就递增了。
这提示我们可以使用动态规划来完成。 如果上面的这些没有听懂，则很有可能对动态规划不熟悉，建议先看下基础知识。
由于题目一定有解，因此交换相邻项中的一个或两个一定能满足两个数组都递增的条件。换句话说，如下的情况是不可能存在的：
A:[1,2,4]
B:[1,5,1]
因为无论怎么交换都无法得到两个递增的序列。那相邻数字的大小关系究竟有哪些呢？实际上大小关系一共有四种。为了描述方便，先列举两个条件，之后直接用 q1 和 q2 来引用这两个关系。
q1：A[i-1] < A[i] and B[i-1] < B[i]
q2：A[i-1] < B[i] and B[i-1] < A[i]
- q1 表示的是两个数组本身就已经递增了，你可以选择不交换。
- q2 表示的是两个数组必须进行一次交换，你可以选择交换 i 或者交换 i - 1。
铺垫已经有了，接下来我们来看下这四种关系。
关系一：q1 满足 q2 满足。换不换都行，换 i 或者 i - 1 都行, 也可以都换
关系二：q1 不满足 q2 不满足。无解，对应上面我举的不可能存在的情况
关系三：q1 满足 q2 不满足。换不换都行，但是如果换需要都换。
关系四：q1 不满足 q2 满足 。必须换，换 i 或者 i - 1
接下来按照上面的四种关系进行模拟即可解决。
- 无需考虑全部整体，而只需要考虑相邻两个数字即可
- 分情况讨论
- 从题目的一定有解条件入手
- 语言支持：Python3
Python3 Code:
class Solution:
def minSwap(self, A: List[int], B: List[int]) -> int:
n = len(A)
swap = [n] * n
no_swap = [n] * n
swap[0] = 1
no_swap[0] = 0
for i in range(1, len(A)):
q1 = A[i-1] < A[i] and B[i-1] < B[i]
q2 = A[i-1] < B[i] and B[i-1] < A[i]
if q1 and q2:
no_swap[i] = min(swap[i-1], no_swap[i-1]) # 都不换或者换i-1
swap[i] = min(swap[i-1], no_swap[i-1]) + 1 # 都换 或者 换 i
if q1 and not q2:
swap[i] = swap[i-1] + 1 # 都换
no_swap[i] = no_swap[i-1] # 都不换
if not q1 and q2:
swap[i] = no_swap[i-1] + 1 # 换 i
no_swap[i] = swap[i-1] # 换 i - 1
return min(swap[n-1], no_swap[n-1])
实际上，我们也可以将逻辑进行合并，这样代码更加简洁。力扣中国题解区很多都是这种写法。即：
if q1:
no_swap[i] = no_swap[i-1] # 都不换
swap[i] = swap[i-1] + 1 # 都换
if q2:
swap[i] = min(swap[i], no_swap[i-1] + 1) # 换 i
no_swap[i] = min(no_swap[i], swap[i-1]) # 换 i - 1
可以看出，这种写法和上面逻辑是一致的。
逻辑合并之后的代码，更简短。但由于两个分支可能都执行到，因此不太容易直接写出。
代码：
class Solution:
def minSwap(self, A: List[int], B: List[int]) -> int:
n = len(A)
swap = [n] * n
no_swap = [n] * n
swap[0] = 1
no_swap[0] = 0
for i in range(1, len(A)):
# 如果交换之前有序，则可以不交换
if A[i-1] < A[i] and B[i-1] < B[i]:
no_swap[i] = no_swap[i-1]
swap[i] = swap[i-1] + 1
# 否则至少需要交换一次（交换当前项或者前一项）
if A[i-1] < B[i] and B[i-1] < A[i]:
swap[i] = min(swap[i], no_swap[i-1] + 1) # i 换
no_swap[i] = min(no_swap[i], swap[i-1]) # i - 1 换
return min(swap[n-1], no_swap[n-1])
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago