Java?C++算法題解leetcode801使序列遞增的最小交換次數(shù)

更新時間：2022年10月10日 17:13:03 作者：AnjaVon

這篇文章主要為大家介紹了Java?C++題解leetcode801使序列遞增的最小交換次數(shù)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路：狀態(tài)機(jī)DP

實(shí)現(xiàn)一：狀態(tài)機(jī)

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]);
    }
}

時間復(fù)雜度：O(n)
空間復(fù)雜度：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]);
    }
};

時間復(fù)雜度：O(n)
空間復(fù)雜度：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
    }
}

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

實(shí)現(xiàn)二：滾動數(shù)組

因為狀態(tài)變換僅依賴于前一項，所以可以改為使用滾動數(shù)組優(yōu)化空間;
- 也就是把dp數(shù)組從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]);
    }
}

時間復(fù)雜度：O(n)
空間復(fù)雜度：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]);
    }
};

時間復(fù)雜度：O(n)
空間復(fù)雜度：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
    }
}