题目要求
思路：状态机DP
实现一：状态机
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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)
Rust
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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)
实现二：滚动数组
- 因为状态变换仅依赖于前一项，所以可以改为使用滚动数组优化空间;
- 也就是把dp数组从n×2改为2×2大小，idx模1交替存储。
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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(1)
Rust
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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(1)
总结
这个不用操作原数组直接改状态的思路还有一点绕，看了好几遍题解又推了几个例子才理解过来。
