資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中使序列遞增的最小交換次數
假設我們有兩個相同非零長度的整數序列 A 和 B。我們可以交換元素 A[i] 和 B[i]。我們必須記住，這兩個元素在其各自序列中的索引位置相同。在完成若干次交換後，A 和 B 都嚴格遞增。我們必須找到使這兩個序列都嚴格遞增的最小交換次數。
因此，如果輸入類似於 A = [1,3,5,4] 和 B = [1,2,3,7]，則答案將是 1，如果我們交換 A[3] 和 B[3]，則序列將變為 A = [1,3,5,7] 和 B = [1,2,3,4]，兩者都嚴格遞增。
為了解決這個問題，我們將遵循以下步驟：
n := A 陣列的大小，建立兩個大小為 n 的陣列 swapCnt 和 noSwapCnt
將 1 插入 swapCnt 並將 0 插入 noSwapCnt
對於 i 從 1 到 n – 1
swapCnt[i] := n 和 noSwapCnt := n
如果 A[i] > A[i – 1] 並且 B[i] > B[i – 1]，則
noSwapCnt[i] := noSwapCnt[i – 1]
swapCnt[i] := swapCnt[i – 1] + 1
如果 A[i] > B[i – 1] 且 B[i] > A[i – 1]，則
swapCnt[i] := swapCnt[i]，1 + noSwapCnt[i – 1] 的最小值
noSwapCnt[i] := swapCnt[i – 1]，noSwapCnt[i] 的最小值
返回 swapCnt[n – 1]，noSwapCnt[n – 1] 的最小值
示例（C++）
讓我們看看以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSwap(vector<int>& A, vector<int>& B) {
int n = A.size();
vector <int> swapCnt(n), noSwapCnt(n);
swapCnt[0] = 1;
noSwapCnt[0] = 0;
for(int i = 1; i < n; i++){
swapCnt[i] = n;
noSwapCnt[i] = n;
if(A[i] > A[i - 1] && B[i] > B[i - 1]){
noSwapCnt[i] = noSwapCnt[i - 1];
swapCnt[i] = swapCnt[i - 1] + 1;
}
if(A[i] > B[i - 1] && B[i] > A[i - 1]){
swapCnt[i] = min(swapCnt[i], 1 + noSwapCnt[i - 1]);
noSwapCnt[i] = min(swapCnt[i - 1], noSwapCnt[i]);
}
}
return min(swapCnt[n - 1], noSwapCnt[n - 1]);
}
};
main(){
vector<int> v1 = {1,3,5,4};
vector<int> v2 = {1,2,3,7};
Solution ob;
cout << (ob.minSwap(v1, v2));
}輸入
[1,3,5,4] [1,2,3,7]
輸出
1
更新於: 2020年5月2日
265 次瀏覽
廣告