跳至主要內容

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

ITCharge大约 4 分钟

0801. 使序列递增的最小交换次数open in new window

  • 标签:数组、动态规划
  • 难度:困难

题目链接

题目大意

给定两个长度相等的整形数组 A 和 B。可以交换两个数组相同位置上的元素,比如 A[i] 与 B[i] 交换,可以交换多个位置,但要保证交换之后保证数组 A和数组 B 是严格递增的。

要求:返回使得数组 A和数组 B 保持严格递增状态的最小交换次数。假设给定的输入一定有效。

解题思路

可以用动态规划来做。

对于两个数组每一个位置上的元素 A[i] 和 B[i] 来说,只有两种情况:换或者不换。

动态规划的状态 dp[i][j] 表示为:第 i 个位置元素,不交换(j = 0)、交换(j = 1)状态时的最小交换次数。

如果数组元素个数只有一个,则:

  • dp[0][0] = 0 ,第 0 个元素不做交换,交换次数为 0。
  • dp[0][1] = 1,第 0 个元素做交换,交换次数为 1。

如果有 2 个元素,为了保证两个数组中的相邻元素都为递增元素,则第 2 个元素交换与否与第 1 个元素有关。同理如果有多个元素,那么第 i 个元素交换与否,只与第 i - 1 个元素有关。现在来考虑第 i 个元素与第 i - 1 的元素的情况。

先按原本数组当前是否满足递增关系来划分,可以划分为:

  • 原本数组都满足递增关系,即 A[i - 1] < A[i] 并且 B[i - 1] < B[i]
  • 不满足上述递增关系的情况,即 A[i - 1] >= A[i] 或者 B[i - 1] >= B[i]

可以看出,不满足递增关系的情况下是肯定要交换的。只需要考虑交换第 i 位元素,还是第 i - 1 位元素。

  • dp[i][0] = dp[i - 1][1],第 i 位若不交换,则第 i - 1 位必须交换。
  • dp[i][1] = dp[i - 1][0] + 1,第 i 位交换,则第 i - 1 位不能交换。

下面再来考虑原本数组都满足递增关系的情况。考虑两个数组间相邻元素的关系。

  • A[i - 1] < B[i] 并且 B[i - 1] < A[i]
  • A[i - 1] >= B[i] 或者 B[i - 1] >= A[i]

如果是 A[i - 1] < B[i] 并且 B[i - 1] < A[i] 情况下,第 i 位交换,与第 i - 1 位交换与否无关,则 dp[i][j] 只需取 dp[i-1][j] 上较小结果进行计算即可,即:

  • dp[i][0] = min(dp[i-1][0], dp[i-1][1])
  • dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1

如果是 A[i - 1] >= B[i] 或者 B[i - 1] >= A[i] 情况下,则如果第 i 位交换,则第 i - 1 位必须跟着交换。如果第 i 位不交换,则第 i - 1 为也不能交换,即:

  • dp[i][0] = dp[i - 1][0],如果第 i 位不交换,则第 i - 1 位也不交换。
  • dp[i][1] = dp[i - 1][1] + 1,如果第 i 位交换,则第 i - 1 位也必须交换。

这样就考虑了所有的情况,最终返回最后一个元素,(交换、不交换)状态下的最小值即可。

代码

class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        size = len(nums1)
        dp = [[0 for _ in range(size)] for _ in range(size)]
        dp[0][1] = 1
        for i in range(1, size):
            if nums1[i - 1] < nums1[i] and nums2[i - 1] < nums2[i]:
                if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]:
                    # 第 i 位交换,与第 i - 1 位交换与否无关
                    dp[i][0] = min(dp[i-1][0], dp[i-1][1])
                    dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1
                else:
                    # 如果第 i 位不交换,则第 i - 1 位也不交换
                    # 如果第 i 位交换,则第 i - 1 位也必须交换
                    dp[i][0] = dp[i - 1][0]
                    dp[i][1] = dp[i - 1][1] + 1
            else:
                dp[i][0] = dp[i - 1][1]         # 如果第 i 位若不交换,则第 i - 1 位必须交换
                dp[i][1] = dp[i - 1][0] + 1     # 如果第 i 位交换,则第 i - 1 位不能交换
        return min(dp[size - 1][0], dp[size - 1][1])