LeetCode_动态规划_困难_801.使序列递增的最小交换次数

àì夳堔傛蜴生んèń 2023-10-07 20:13 46阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

我们有两个长度相等且不为空的整型数组 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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing

## 2.思路 ##

（1）动态规划  
思路参考[本题官方题解][Link 1]。

① 由于用例保证可以实现操作，并且每次只能交换相同位置的两个数，所以位置 i 一定至少满足以下两种情况中的一种：

情况1：nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i];  //无需交换
    情况2：nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i];	//需要交换

② 定义 dp 数组，设 dp\[i\]\[0\] 表示到位置 i 为止使数组 nums1 和 nums2 满足严格递增并且位置 i 不进行交换操作的最小操作数，dp\[i\]\[1\] 表示到位置 i 为止使数组 nums1 和 nums2 满足严格递增并且位置 i 进行交换操作的最小操作数。

int[][] dp = new int[length][2];

③ 分析状态转移方程：  
1）只满足情况 1：

dp[i][0] = dp[i - 1][0];
    dp[i][1] = dp[i - 1][1] + 1;

2）只满足情况 2：

dp[i][0] = dp[i - 1][1];
    dp[i][1] = dp[i - 1][0] + 1;

3）同时满足情况 1 和情况 2：

dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1]);
    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;

④ 初始化 dp，当 i = 0 时，此时无论是否交换都满足题意，即 dp\[0\]\[0\] = 0，dp\[0\]\[1\] = 1。此外，上面求解的每一个状态都只与前一个状态相关，所以我们可以使用**滚动数组**来降低空间复杂度。

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public int minSwap(int[] nums1, int[] nums2) {
        
            int length = nums1.length;
            /*
                设 dp[i][0] 表示到位置 i 为止使数组 nums1 和 nums2 满足严格递增并且位置 i 不进行交换操作的最小操作数
                设 dp[i][1] 表示到位置 i 为止使数组 nums1 和 nums2 满足严格递增并且位置 i 进行交换操作的最小操作数
            */
            int[][] dp = new int[length][2];
            dp[0][1] = 1;
            for (int i = 1; i < length; i++) {
        
                //位置 i 一定至少满足以下两种情况中的一种：
                boolean situation1 = nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i];
                boolean situation2 = nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i];
                if (situation1) {
        
                    dp[i][0] = dp[i - 1][0];
                    dp[i][1] = dp[i - 1][1] + 1;
                }
                if (situation2) {
        
                    dp[i][0] = dp[i - 1][1];
                    dp[i][1] = dp[i - 1][0] + 1;
                }
                if (situation1 && situation2) {
        
                    dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1]);
                    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
                }
            }
            return Math.min(dp[length - 1][0], dp[length - 1][1]);
        }
    }
    
    //使用滚动数组降低空间复杂度
    class Solution {
        
        public int minSwap(int[] nums1, int[] nums2) {
        
            int length = nums1.length;
            // dp[0][0] = 0, dp[0][1] = 1
            int a = 0, b = 1;
            for (int i = 1; i < length; i++) {
        
                //因为每次只能交换相同位置的两个数，所以位置 i 一定至少满足以下两种情况中的一种：
                boolean situation1 = nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i];
                boolean situation2 = nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i];
                int at = a, bt = b;
                a = b = length;
                if (situation1) {
        
                    a = Math.min(a, at);
                    b = Math.min(b, bt + 1);
                }
                if (situation2) {
        
                    a = Math.min(a, bt);
                    b = Math.min(b, at + 1);
                }
            }
            return Math.min(a, b);
        }
    }

[Link 1]: https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing/solution/shi-xu-lie-di-zeng-de-zui-xiao-jiao-huan-ux2y/