每日一题做题记录，参考官方和三叶的题解

题目要求

思路：状态机DP

• 首先注意交换是在两数组的相同位置上，所以仅需考虑其与前后元素的大小即可，又由于从前向后遍历，所以仅考虑和其前一位置元素大小关系即可。
• 定义数组f[idx][state]f[idx][state]f[idx][state]作为状态数组，表示位置为iii的元素交换状态为statestatestate【交换为111，反之为000】时使前续的数组满足严格递增的最小交换次数，所以最终答案即为n−1n-1n−1位置元素的最小交换次数，即min⁡(f[n−1][0],f[n−1][1])\min(f[n-1][0],f[n-1][1])min(f[n−1][0],f[n−1][1])；
  • 因为和前一位置元素比较，所以从位置111开始遍历，初始化f[0][0]=0f[0][0]=0f[0][0]=0【000位置不交换】、f[0][1]=1f[0][1]=1f[0][1]=1【000位置交换，次数为111】，其他初始化为大于数组长度的值；
  • 考虑不同情况下的状态转移，当前遍历到位置iii：
    • 若两数组各自满足递增，即nums1[i−1]<nums1[i]nums1[i-1]<nums1[i]nums1[i−1]<nums1[i]且nums2[i−1]<nums2[i]nums2[i-1]<nums2[i]nums2[i−1]<nums2[i]，此时仅交换一个位置则可能打破递增关系，需要同时交换两个位置或两个位置都不交换：
      • 两个位置都不换，状态从不换000到不换000：f[i][0]=f[i−1][0]f[i][0]=f[i-1][0]f[i][0]=f[i−1][0]；
      • 两个位置都换，状态从111到111：f[i][1]=f[i−1][1]+1f[i][1]=f[i-1][1]+1f[i][1]=f[i−1][1]+1，加上本次交换；
      • 【这里最开始不是很懂，只换一个也是能够满足条件的，比如数组2、4和3、5，这种情况怎么办呢？所以出现了下一个若……】
    • 若两数组交叉满足条件，即nums2[i−1]<nums1[i]nums2[i-1]<nums1[i]nums2[i−1]<nums1[i]且nums1[i−1]<nums2[i]nums1[i-1]<nums2[i]nums1[i−1]<nums2[i]，此时仅可交换一个位置：
      • 换前者，状态从111到000：f[i][0]=min⁡(f[i][0],f[i−1][1])f[i][0]=\min(f[i][0],f[i-1][1])f[i][0]=min(f[i][0],f[i−1][1])；
      • 换后者，状态从000到111：f[i][1]=min⁡(f[i][1],f[i−1][0]+1)f[i][1]=\min(f[i][1],f[i-1][0]+1)f[i][1]=min(f[i][1],f[i−1][0]+1)，加上本次交换；
      • min⁡\minmin就是因为这个位置可能在上一个若中更新过，判断一下哪种最优取哪种作为最终结果。
    • 其他情况交换也解决不了所以无需更新状态，直接略过。

实现一：状态机

Java

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[][] f = new int[n][2];
        for (int i = 1; i < n; i++)
            f[i][0] = f[i][1] = n + 10; // 初始化
        f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                f[i][0] = Math.min(f[i][0], f[i - 1][1]);
                f[i][1] = Math.min(f[i][1], f[i - 1][0] + 1); 
            }
        }
        return Math.min(f[n - 1][0], f[n - 1][1]);
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(n)O(n)O(n)

C++

class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int f[n][2];
        for (int i = 1; i < n; i++)
            f[i][0] = f[i][1] = n + 10; // 初始化
        f[0][0] = 0;
        f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                f[i][0] = min(f[i][0], f[i - 1][1]);
                f[i][1] = min(f[i][1], f[i - 1][0] + 1); 
            }
        }
        return min(f[n - 1][0], f[n - 1][1]);
    }
};

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(n)O(n)O(n)

Rust

impl Solution {
    pub fn min_swap(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let n = nums1.len();
        let mut f = vec![vec![n + 10; 2 as usize]; n as usize];
        f[0][0] = 0;
        f[0][1] = 1;
        for i in 1..n {
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                f[i][0] = f[i][0].min(f[i - 1][1]);
                f[i][1] = f[i][1].min(f[i - 1][0] + 1); 
            }
        }
        f[n - 1][0].min(f[n - 1][1]) as i32
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(n)O(n)O(n)

实现二：滚动数组

• 因为状态变换仅依赖于前一项，所以可以改为使用滚动数组优化空间;
  • 也就是把dp数组从n×2n\times 2n×2改为2×22\times22×2大小，idxidxidx模111交替存储。

Java

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[][] f = new int[2][2];
        f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            int tru = n + 10, fal = n + 10; // 暂存
            int pre = (i - 1) & 1, cur = i & 1;
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                tru = f[pre][0];
                fal = f[pre][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                tru = Math.min(tru, f[pre][1]);
                fal = Math.min(fal, f[pre][0] + 1); 
            }
            // 更新
            f[cur][0] = tru;
            f[cur][1] = fal;
        }
        return Math.min(f[(n - 1) & 1][0], f[(n - 1) & 1][1]);
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

C++

class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int f[2][2];
        f[0][0] = 0;
        f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            int tru = n + 10, fal = n + 10; // 暂存
            int pre = (i - 1) & 1, cur = i & 1;
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                tru = f[pre][0];
                fal = f[pre][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                tru = min(tru, f[pre][1]);
                fal = min(fal, f[pre][0] + 1); 
            }
            // 更新
            f[cur][0] = tru;
            f[cur][1] = fal;
        }
        return min(f[(n - 1) & 1][0], f[(n - 1) & 1][1]);
    }
};

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

Rust

impl Solution {
    pub fn min_swap(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let n = nums1.len();
        let mut f = vec![vec![n + 10; 2 as usize]; 2 as usize];
        f[0][0] = 0;
        f[0][1] = 1;
        for i in 1..n {
            let (mut tru, mut fal) = (n + 10, n + 10);
            let (pre, cur) = ((i - 1) & 1, i & 1);
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                tru = f[pre][0];
                fal = f[pre][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                tru = tru.min(f[pre][1]);
                fal = fal.min(f[pre][0] + 1); 
            }
            f[cur][0] = tru;
            f[cur][1] = fal;
        }
        f[(n - 1) & 1][0].min(f[(n - 1) & 1][1]) as i32
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

总结

• 这个不用操作原数组直接改状态的思路还有一点绕，看了好几遍题解又推了几个例子才理解过来。
• 是快乐推导快乐代码的一天~
• 好的快乐完了开始苦逼打工……

欢迎指正与讨论！