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

标签: 数组 动态规划

难度: Hard

我们有两个长度相等且不为空的整型数组 nums1 和 nums2 。在一次操作中，我们可以交换 nums1[i] 和 nums2[i]的元素。

  • 例如，如果 nums1 = [1,2,3,8] ， nums2 =[5,6,7,4] ，你可以交换 i = 3 处的元素，得到 nums1 =[1,2,3,4] 和 nums2 =[5,6,7,8] 。

返回 使 nums1 和 nums2 严格递增 所需操作的最小次数 。

数组 arr 严格递增 且  arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1] 。

注意：

  • 用例保证可以实现操作。

示例 1:

输入: nums1 = [1,3,5,4], nums2 = [1,2,3,7]
输出: 1
解释: 
交换 A[3] 和 B[3] 后，两个数组如下:
A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
两个数组均为严格递增的。

示例 2:

输入: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]
输出: 1

提示:

  • 2 <= nums1.length <= 105
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 2 * 105

Submission

运行时间: 87 ms

内存: 30.6 MB

class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        a, b = 0, 1
        for i in range(1, len(nums1)):
            x, y = a, b
            if nums1[i - 1] >= nums1[i] or nums2[i - 1] >= nums2[i]:
                a, b = y, x + 1
            else:
                b = y + 1
                if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]:
                    a, b = min(a, y), min(b, x + 1)
        return min(a, b)

Explain

这个题解使用了动态规划的思想。定义了两个变量a和b，分别表示当前位置i不交换和交换时的最小交换次数。然后从第二个位置开始遍历数组，对于每个位置，根据前一个位置的状态和当前位置的大小关系，更新a和b的值。最后返回a和b中的较小值即为最小交换次数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        a, b = 0, 1  # a表示当前位置不交换的最小交换次数，b表示当前位置交换的最小交换次数
        for i in range(1, len(nums1)):
            x, y = a, b  # 保存上一个位置的a和b的值
            if nums1[i - 1] >= nums1[i] or nums2[i - 1] >= nums2[i]:  # 如果当前位置不满足严格递增条件
                a, b = y, x + 1  # 当前位置必须交换，更新a和b
            else:  # 如果当前位置满足严格递增条件
                b = y + 1  # 当前位置交换，b更新为上一个位置交换的最小交换次数加1
                if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]:  # 如果交叉满足严格递增条件
                    a, b = min(a, y), min(b, x + 1)  # 当前位置可以选择交换或不交换，取较小值
        return min(a, b)  # 返回最后一个位置的a和b中的较小值

Explore

在动态规划的这个问题中，`a`和`b`分别代表不进行交换和进行交换的最小交换次数。初始时，`a`被设置为0，因为在第一个元素位置我们假定没有进行任何交换，因此交换次数为0。而`b`设置为1表示第一个元素我们选择进行了交换，因此初始交换次数为1。这种设置是为了在动态规划过程中正确地追踪和计算不同位置上的交换情况和所需的最小交换次数。

当`nums1[i - 1] >= nums1[i]`或`nums2[i - 1] >= nums2[i]`出现时，这意味着数组的这一部分不满足严格递增的条件，因此需要进行操作以保持递增序列。设置`a`为`y`（即前一个位置的`b`值）表示如果前一个位置进行了交换，当前位置不交换也能保持递增。将`b`设置为`x + 1`（即前一个位置的`a`值加1）表示如果前一个位置没有交换，当前位置必须交换来维持递增。这种设置确保了无论如何都能通过适当的交换来维持整个数组的严格递增顺序。

当`nums1[i - 1] < nums2[i]`和`nums2[i - 1] < nums1[i]`，即两种交叉的大小关系都满足时，表示无论是交换还是不交换，都可以维持严格递增的条件。在代码中，这种情况通过更新`a`和`b`来体现：`a = min(a, y)`和`b = min(b, x + 1)`。这里的`min`函数确保无论是选择交换还是不交换，都能取得当前位置可能的最小交换次数。这种灵活的选择使得整体的交换次数尽可能地小。

在动态规划中，每个位置的决策可能依赖于前一个位置的状态（交换或不交换），并且每个位置都可能面临不同的选择条件（如数组元素的大小关系）。因此，我们不能简单地从前一个位置的结果直接推断出当前位置的最优解，而需要基于当前的具体情况重新计算`a`和`b`。这种重新计算确保了每一步都是基于当前最全面信息的最优决策，从而得到全局的最小交换次数。