Java&C++題解與拓展——leetcode801.使序列遞增的最小交換次數【麼的新知識】
theme: hydrogen highlight: atom-one-dark
| 每日一題做題記錄，參考官方和三葉的題解 |
題目要求
思路：狀態機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$就是因為這個位置可能在上一個若中更新過，判斷一下哪種最優取哪種作為最終結果。
- 其他情況交換也解決不了所以無需更新狀態，直接略過。
- 若兩陣列各自滿足遞增，即$nums1[i-1]<nums1[i]$且$nums2[i-1]<nums2[i]$，此時僅交換一個位置則可能打破遞增關係，需要同時交換兩個位置或兩個位置都不交換：
實現一：狀態機
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)$
總結
- 這個不用操作原陣列直接改狀態的思路還有一點繞，看了好幾遍題解又推了幾個例子才理解過來。
- 是快樂推導快樂程式碼的一天~
- 好的快樂完了開始苦逼打工……
| 歡迎指正與討論！ |