Java和C++怎么实现序列递增的最小交换次数

2023-06-15 10:26:32 序列 递增 最小

本篇内容主要讲解“Java和C++怎么实现序列递增的最小交换次数”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Java和C++怎么实现序列递增的最小交换次数”吧!

    题目要求

    Java和C++怎么实现序列递增的最小交换次数

    Java和C++怎么实现序列递增的最小交换次数

    思路:状态机DP

    Java和C++怎么实现序列递增的最小交换次数

    实现一:状态机

    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&times;2改为2&times;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)

    相关文章