Java&C++題解與拓展——leetcode801.使序列遞增的最小交換次數【麼的新知識】

語言: CN / TW / HK

theme: hydrogen highlight: atom-one-dark


每日一題做題記錄,參考官方和三葉的題解

題目要求

image.png

image.png

思路:狀態機DP

  • 首先注意交換是在兩陣列的相同位置上,所以僅需考慮其與前後元素的大小即可,又由於從前向後遍歷,所以僅考慮和其前一位置元素大小關係即可。
  • 定義陣列$f[idx][state]$作為狀態陣列,表示位置為$i$的元素交換狀態為$state$【交換為$1$,反之為$0$】時使前續的陣列滿足嚴格遞增的最小交換次數,所以最終答案即為$n-1$位置元素的最小交換次數,即$\min(f[n-1][0],f[n-1][1])$;
    • 因為和前一位置元素比較,所以從位置$1$開始遍歷,初始化$f[0][0]=0$【$0$位置不交換】、$f[0][1]=1$【$0$位置交換,次數為$1$】,其他初始化為大於陣列長度的值;
    • 考慮不同情況下的狀態轉移,當前遍歷到位置$i$:
      • 若兩陣列各自滿足遞增,即$nums1[i-1]<nums1[i]$且$nums2[i-1]<nums2[i]$,此時僅交換一個位置則可能打破遞增關係,需要同時交換兩個位置或兩個位置都不交換:
        • 兩個位置都不換,狀態從不換$0$到不換$0$:$f[i][0]=f[i-1][0]$;
        • 兩個位置都換,狀態從$1$到$1$:$f[i][1]=f[i-1][1]+1$,加上本次交換;
        • 【這裡最開始不是很懂,只換一個也是能夠滿足條件的,比如陣列2、4和3、5,這種情況怎麼辦呢?所以出現了下一個……】
      • 若兩陣列交叉滿足條件,即$nums2[i-1]<nums1[i]$且$nums1[i-1]<nums2[i]$,此時僅可交換一個位置:
        • 換前者,狀態從$1$到$0$:$f[i][0]=\min(f[i][0],f[i-1][1])$;
        • 換後者,狀態從$0$到$1$:$f[i][1]=\min(f[i][1],f[i-1][0]+1)$,加上本次交換;
        • $\min$就是因為這個位置可能在上一個若中更新過,判斷一下哪種最優取哪種作為最終結果。
      • 其他情況交換也解決不了所以無需更新狀態,直接略過。

實現一:狀態機

Java

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++

cpp 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

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\times2$大小,$idx$模$1$交替儲存。

Java

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++

cpp 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

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)$

總結

  • 這個不用操作原陣列直接改狀態的思路還有一點繞,看了好幾遍題解又推了幾個例子才理解過來。
  • 是快樂推導快樂程式碼的一天~
  • 好的快樂完了開始苦逼打工……


歡迎指正與討論!