C++ 中使序列递增的最小交换次数
c++server side programmingprogramming
假设我们有两个长度相同的非零整数序列 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
对于范围为 1 到 n 的 i – 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
