最小交换到相对排序两个数组

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

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

首先，我们定义一个辅助函数，用于检查交换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-th的迭代i = 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)。我们的循环步骤将考虑四种情况：

• 我们不交换 at i，也不交换 at i + 1；最佳的：prevNoSwap，
• 我们在 处交换i，我们不在 处交换i + 1；最佳的：prevNoSwap + 1，
• 我们不交换 at i，我们交换 at i + 1；最佳的：prevSwap，
• 我们在 处交换i，我们不在 处交换i + 1；最佳的：prevSwap + 1。

如果给定的案例创建了有效的解决方案，我们会将其视为可能的步骤数。我们按swapping / not swappingat将它们分组i并取最小值。我们假设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()