您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“Java和C++怎么實(shí)現(xiàn)序列遞增的最小交換次數(shù)”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Java和C++怎么實(shí)現(xiàn)序列遞增的最小交換次數(shù)”吧!
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)
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)
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)
因?yàn)闋顟B(tài)變換僅依賴于前一項(xiàng),所以可以改為使用滾動數(shù)組優(yōu)化空間;
也就是把dp數(shù)組從n×2改為2×2大小,idx模1交替存儲。
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)
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)
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 } }
時間復(fù)雜度:O(n)
空間復(fù)雜度:O(1)
到此,相信大家對“Java和C++怎么實(shí)現(xiàn)序列遞增的最小交換次數(shù)”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。