将两个数组相对排序的最小交换次数

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);
}

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

此外，我想知道是否可以使用动态规划来解决这个问题。如果是，请问应该在表格中存储哪种状态？应该采取什么方法？

- Nisha

---

是的，如果您添加您使用的代码，那将有助于读者。 - 0xCursor

如果无法进行相对排序，则必须返回 -1。 - Nisha

@LAD 是的，OP需要更详细地说明。即使最多只有2个重复的整数，也可能存在无法实现的状态，例如[1,5,9]和[2,3,3]。我认为，假设只给出有效的输入，那么这个问题并不像看起来那么棘手。 - nice_dev

@Nisha，那很有道理。你可能想在帖子中说明这一点。 - 0xCursor

@Nisha 如果我们对它们进行单独排序并对它们应用相对排序，这样可以吗？或者我们不能改变它们的顺序？ - nice_dev

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]);
}

- hitesh sagtani

Answer 2

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

首先，让我们定义一个辅助函数，检查我们交换第i个和/或第i + 1个元素后是否获得了局部有效的解决方案。我所说的局部有效是仅考虑这四个数字。

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 = x.length - 2 downto 0 的 i-th 迭代。

• 最优交换次数是多少，以便索引 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。

如果给定的情况可以创建有效解决方案，则将其视为可能的步骤数。我们按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()

- bottaio

---

嗨，谢谢你的回答。虽然我理解大部分内容，但由于我不熟悉编写过于复杂的伪代码，所以我有些困惑。这里没有PreSwap和withPreSwap数组吗？ - Nisha