0801. 使序列递增的最小交换次数

题目地址(801. 使序列递增的最小交换次数)

https://leetcode-cn.com/problems/minimum-swaps-to-make-sequences-increasing/

题目描述

我们有两个长度相等且不为空的整型数组 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。

最后更新于