对两个数组进行相对排序的最小交换

Question

给定两个数组arr1和arr2，我们必须找到最小交换，以相对地将两个数组按严格的递增顺序排序。如果无法进行相对排序，则返回 -1。

相对排序定义为交换arr1和arr2的相同索引元素。

即相对排序的步骤：

swap(arr1[i], arr2[i])

严格递增顺序定义为：

arr[i+1]>arr[i] for all i

例：

arr1={1,4,4,9} 
arr2={2,3,5,10}

那么最小交换是 1，因为交换arr1[2]和arr2[2]将使两个数组严格增加。 我使用递归解决了这个问题。 如果arr[i]>arr[i+1]，我们可以交换索引i的元素或索引i+1的元素，然后调用索引i+1的函数。我试图找到两个值中的最小值并返回它。每个索引都遵循此过程i。

int f(int N, int *arr1, int *arr2, int i){
if(i == N-1)
return 0;
if(arr1[i]>=arr1[i+1] && arr2[i]>=arr2[i+1])return -1;
if(arr1[i]>=arr1[i+1] || arr2[i]>=arr2[i+1]){
int m, n;
swap(arr1[i], arr2[i]);
m = f(N, arr1, arr2, i+1);
swap(arr1[i], arr2[i]);
swap(arr1[i+1, arr2[i+1]);
n = f(N, arr1, arr2, i+1);
if(m == -1 && n==-1)return -1;
if(m==-1)return n;
if(n==-1)return m;
return min(m, n);
}
return f(N, arr1, arr2, i+1);
}
int minSwaps(int N, int *arr1, int *arr2){
return f(N, arr1, arr2, 0);
}

由于这是我在在线编码测试中遇到的问题，因此我通过了基本测试用例，但我仍然不确定此方法是否适用于所有测试用例。

另外，我想知道这个问题是否可以使用动态编程来解决。如果是，表中应存储什么状态？应该采取什么方法？

Answer 1

int minSwap(vector<int>& a, vector<int>& b){
int inf = (int)(1e9);
int n=a.size();
int dp[n][2];
dp[0][0]=0;
dp[0][1]=1;
for(int i=1;i<n;i++)
dp[i][0]=dp[i][1]=inf;
for(int i=1;i<n;i++){
if(a[i-1]<a[i]&&b[i-1]<b[i]){
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1]+1;
}
if(a[i-1]<b[i]&&b[i-1]<a[i]){
dp[i][0]=min(dp[i][0],dp[i-1][1]);
dp[i][1]=min(dp[i][1],dp[i-1][0]+1);
}
}
return min(dp[n-1][0],dp[n-1][1]);
}

Answer 2

您的解决方案在数组大小上呈指数级增长。正如您在问题中注意到的那样，可以使用动态规划获得解决方案。

首先，让我们定义一个帮助函数，用于检查交换元素后是否i-th and/or i + 1-st获得本地有效的解决方案。我所说的局部有效是指只考虑这四个数字。

def isValid(i, preSwap, postSwap):
val lx = if (preSwap) y(i) else x(i)
val rx = if (postSwap) y(i + 1) else x(i + 1)
val ly = if (preSwap) x(i) else y(i)
val ry = if (postSwap) x(i + 1) else y(i + 1)
// x(i) < x(i + 1) && y(i) < y(i + 1)
lx < rx && ly < ry

现在，我们将简单地向后循环数组。我们的动态编程内存将是恒定的 - 我们只需要记住两个整数。让我们考虑i-thi = x.length - 2 downto 0迭代。

• 什么是最佳掉期次数，以便指示i + 1 upto x.length - 1排序越来越好，x(i)和y(i)不被交换，
• 交换的最佳数量是多少，以便指示i + 1 upto x.length - 1排序越来越高，交换x(i)和y(i)。

对于长度列表1我们得到一个元组(prevNoSwap, prevSwap) = (0, 1)。我们的循环步骤将考虑四种情况：

• 我们不会在i时交换，也不会在i + 1时交换; 最优：prevNoSwap，
• 我们在i交换，我们不在i + 1交换;最优：prevNoSwap + 1，
• 我们不在i交换，而是在i + 1交换;最优：prevSwap，
• 我们在i交换，我们不在i + 1交换;最优：prevSwap + 1。

如果给定的情况创建了有效的解决方案，我们会将其视为可能的步骤数。我们按iswapping / not swapping对它们进行分组，并采用最小值。我们假设，如果在特定情况下找不到解决方案，这些元素中的任何一个都可能变得Infinity。

循环后，我们至少选择两个元组值。下面是伪代码的其余部分：

state = (0, 1)
for i in x.length - 2 downto 0
noPreSwap, withPreSwap = [#INFINITY], [#INFINITY]
if (isValid(i, preSwap = false, postSwap = false)) noPreSwap += state.left
if (isValid(i, preSwap = false, postSwap = true)) noPreSwap += state.right
if (isValid(i, preSwap = true, postSwap = true)) withPreSwap += state.right + 1
if (isValid(i, preSwap = true, postSwap = false)) withPreSwap += state.right
state = (noPreSwap.min(), withPreSwap.min())
return if state.min().isInfinity() -1 else state.min()