801. 使序列递增的最小交换次数（难度：困难）

手机游戏开发者 · 2024-9-12 19:42:46

标题链接：https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing/

标题形貌：

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

例如，如果 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, nums2 <= 2 * 105

解法：动态规划

由于标题用例可以包管交换之后，肯定满意两个数组都是递增的。
我们利用dp[0] 和 dp[1] 来分别记载在第i位交换和不交换必要移动的最少次数。
那么在决定下标i是否交换时，我们可以针对nums1[i-1]、nums1、nums2[i-1]、nums2这四个值来判断那种方式比力符合，着实就只有几种情况了。

当两个数组在第i-1位和第i位原来就满意递增，并且交换后依然满意递增。即 nums1[i-1] < nums1、nums2[i-1] < nums2、nums1[i-1] < nums2、nums2[i-1] < nums1，同时满意上面四个条件时，针对第i位是否交换的两种情况：

i选择【不交换】，则i-1可【交换】也可【不交换】，即 dp[0] = Math.min(dp[i - 1][0], dp[i - 1][1])；

i选择【交换】，则i-1可【交换】也可【不交换】，即dp[1] = dp[0] + 1。

当两个数组在第i-1位和第i位原来就满意递增，并且交换后不满意递增。即 nums1[i-1] < nums1、nums2[i-1] < nums2、nums1[i-1] > nums2或者nums2[i-1] > nums1，同时满意上面四个条件时，针对第i位是否交换的两种情况：

i选择【不交换】，则i-1必须【不交换】，即 dp[0] = dp[i - 1][0]；

i选择【交换】，则i-1必须【交换】，即dp[1] = dp[1] + 1。

当两个数组在第i-1位和第i位一个递增，一个不递增或者两个都不递增，交换一个元素后，两个数组都递增。针对第i位是否交换的两种情况：

i选择【不交换】，则i-1必须【交换】，即 dp[0] = dp[i - 1][1]；

i选择【交换】，则i-1必须【不交换】，即 dp[0] = dp[i - 1][0]；

在遍历竣事后，会得到对应的状态值dp，终极结果为Math.min(dp[nums1.length - 1][0], dp[nums1.length - 1][1]。
代码：

801. 使序列递增的最小交换次数（难度：困难）

所属分类: 问答交流

新帖推荐: 30日

推荐作品