如何通过最小交换次数使序列递增的Java C语言LeetCode 801算法题解？

本文共计1315个文字，预计阅读时间需要6分钟。

目录+主题要求+思路：状态DP+实现一：状态机+Java+C+++Rust+实现二：滚动数组+Java+C+++Rust+总结+主题要求+思路：状态DP+实现一：状态机+Java+class+Solution+{+public+int+minSwap(int[]+nums1,+int[]+n)+}

目录

• 题目要求
• 思路：状态机DP
• 实现一：状态机
• Java
• C++
• Rust
• 实现二：滚动数组
• Java
• C++
• Rust
• 总结

题目要求

思路：状态机DP

实现一：状态机

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)

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)

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)

实现二：滚动数组

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

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(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(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(1)

总结

这个不用操作原数组直接改状态的思路还有一点绕，看了好几遍题解又推了几个例子才理解过来。

以上就是Java C++题解leetcode801使序列递增的最小交换次数的详细内容，更多关于Java C++ 序列递增最小交换次数的资料请关注自由互联其它相关文章！