【力扣 leetcode】801：使序列递增的最小交换次数

比眉伴天荒 2023-10-09 14:54 8阅读 0赞

## 题目 ##

我们有两个长度相等且不为空的整型数组 `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  
> 著作权归领扣网络所有。仅供个人学习，非商用。

## 题解 ##

**方法一：动态规划**  
本题目有一个**隐藏条件**，数组中第 i 位的元素与数组第 i-1 位的元素只有两种可能的关系：

1.  **关系1：**`nums1[i] > nums1[i-1]` 并且 `nums2[i] > nums2[i-1]`
2.  **关系2：**`nums1[i] > nums2[i-1]` 并且 `nums2[i] > nums1[i-1]`

至少要满足其中的一个关系，才能通过交换第 i 位元素，使这两个数组均严格单调递增。  
因此，数组中第 i 位的元素必定属于三种情况之一：

1.  **情况1：** 满足关系 1，不满足关系 2
2.  **情况2：** 不满足关系 1，满足关系 2
3.  **情况3：** 同时满足关系 1 和关系 2

如果有元素不属于以上三种情况之一，则不能通过交换第 i 位元素，使这两个数组均为严格单调递增。我们可以对三种情况进行如下解释：

*  **情况1：**`nums1[i]` 一定要紧跟在 `nums1[i-1]` 的后面。
    
     *  如果第 i-1 位交换元素，则第 i 位必须交换元素。
     *  如果第 i-1 位没有交换元素，则第 i 位一定不能交换元素。
 *  **情况2：**`nums1[i]` 一定要紧跟在 `nums2[i-1]` 的后面。
    
     *  如果第 i-1 位交换元素，则第 i 位一定不能交换元素。
     *  如果第 i-1 位没有交换元素，则第 i 位必须交换元素。
 *  **情况3：**`nums1[i]` 和 `nums2[i]` 都比`nums1[i-1]` 和 `nums2[i-1]`大，因此：
    
     *  如果第 i-1 位交换元素，第 i 位元素可以交换也可以不交换。
     *  如果第 i-1 位不交换元素，第 i 位元素同样可以交换也可以不交换。

我们发现每一位的元素只有交换和不交换元素两种操作，并且第 i 位是否交换元素与第 i-1 位元素有关，我们可以使用数组 `int[][]dp = new [len-1][2]` 存储信息。其中：

*  `dp[i][0]` 表示在第 i 位不交换元素时，使两个数组严格单调递归所需的最小操作次数。
 *  `dp[i][1]` 表示在第 i 位交换元素时，使两个数组严格单调递归所需的最小操作次数。

通过以上分析，我们可以找到**推导规则**：

*  **情况一：**
    
     *  `dp[i][0] = dp[i-1][0];`
     *  `dp[i][1] = dp[i-1][1] + 1;`
 *  **情况二：**
    
     *  `dp[i][0] = dp[i-1][1];`
     *  `dp[i][1] = dp[i-1][0] + 1;`
 *  **情况三：**
    
     *  `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;`

class Solution {
        
        public int minSwap(int[] nums1, int[] nums2) {
        
            int len = nums1.length;
            int[][] dp = new int[len][2];
            dp[0][0] = 0;
            dp[0][1] = 1;
    
            for (int i = 1; i < len; i++){
        
                if (case1(i, nums1, nums2) && !case2(i, nums1, nums2)){
        
                    dp[i][0] = dp[i-1][0];
                    dp[i][1] = dp[i-1][1] + 1;
                }else if (!case1(i, nums1, nums2) && case2(i, nums1, nums2)){
        
                    dp[i][0] = dp[i-1][1];
                    dp[i][1] = dp[i-1][0] + 1;
                }else{
        
                    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 dp[len-1][0] > dp[len-1][1] ? dp[len-1][1] : dp[len-1][0];
        }
    
        public boolean case1(int i, int[] nums1, int[] nums2){
        
            if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1])
                return true;
            return false;
        }
    
        public boolean case2(int i, int[] nums1, int[] nums2){
        
            if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1])
                return true;
            return false;
        }
    }