数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告