求将两个等长数组升序排序所需的最少swap次数

这个问题确实有点 tricky，不过用动态规划就能完美解决！我来一步步给你拆解思路，结合你的示例来验证～

给定两个等长数组，仅允许交换对应索引处的元素，要求最终两个数组都呈升序排列，求最少的交换次数。如果无法达成目标，则返回-1。

我们可以用动态规划来跟踪每个位置的两种状态：交换当前元素或不交换，然后基于前一个位置的状态推导当前的最优解。

状态定义 #

定义两个状态数组（或者用两个变量优化空间）：

• dp[i][0]：处理到第i个位置，不交换A[i]和B[i]时的最少交换次数
• dp[i][1]：处理到第i个位置，交换A[i]和B[i]时的最少交换次数

初始化 #

对于第一个元素（i=0）：

• 不交换的话，次数为0 → dp[0][0] = 0
• 交换的话，次数为1 → dp[0][1] = 1

递推逻辑 #

对于每个后续位置i >= 1，我们需要考虑前一个位置的两种状态（交换/不交换），判断当前位置的操作是否合法：

情况1：前一个位置未交换 #

此时前一个位置的元素是A[i-1]和B[i-1]：

• 如果A[i-1] <= A[i]且B[i-1] <= B[i]：当前位置可以不交换，更新dp[i][0] = min(dp[i][0], dp[i-1][0])
• 如果A[i-1] <= B[i]且B[i-1] <= A[i]：当前位置可以交换，更新dp[i][1] = min(dp[i][1], dp[i-1][0] + 1)

情况2：前一个位置已交换 #

此时前一个位置的元素是B[i-1]和A[i-1]（因为交换过）：

• 如果B[i-1] <= A[i]且A[i-1] <= B[i]：当前位置可以不交换，更新dp[i][0] = min(dp[i][0], dp[i-1][1])
• 如果B[i-1] <= B[i]且A[i-1] <= A[i]：当前位置可以交换，更新dp[i][1] = min(dp[i][1], dp[i-1][1] + 1)

示例验证 #

用你给出的示例A = [1,8,12,11]、B = [7,3,10,15]来走一遍：

1. i=0：dp[0][0]=0，dp[0][1]=1
2. i=1：
   • 前一个未交换：1<=8但7>3，不交换不合法；1<=3且7<=8，交换合法 → dp[1][1] = 0+1=1
   • 前一个已交换：7<=8且1<=3，不交换合法 → dp[1][0] =1；交换不合法
   • 结果：dp[1][0]=1，dp[1][1]=1
3. i=2：
   • 前一个未交换：8<=12且3<=10，不交换合法 → dp[2][0]=1；8<=10且3<=12，交换合法 → dp[2][1]=1+1=2
   • 前一个已交换：3<=12且8<=10，不交换合法 → dp[2][0]保持1；3<=10且8<=12，交换合法 → dp[2][1]保持2
   • 结果：dp[2][0]=1，dp[2][1]=2
4. i=3：
   • 前一个未交换：12>11，不交换不合法；12<=15且10<=11，交换合法 → dp[3][1] =1+1=2
   • 前一个已交换：10<=11且12<=15，不交换合法 → dp[3][0] =2；交换不合法
   • 结果：dp[3][0]=2，dp[3][1]=2

最终取最小值min(2,2)=2，和示例的结果一致。

这里用Python写出完整的实现，还处理了无解的情况：

def min_swap(A, B):
    n = len(A)
    if n == 0:
        return 0
    INF = float('inf')
    # 初始化DP数组，INF表示该状态不可达
    dp = [[INF] * 2 for _ in range(n)]
    dp[0][0] = 0
    dp[0][1] = 1
    
    for i in range(1, n):
        # 前一个位置未交换的情况
        if A[i-1] <= A[i] and B[i-1] <= B[i]:
            dp[i][0] = min(dp[i][0], dp[i-1][0])
        if A[i-1] <= B[i] and B[i-1] <= A[i]:
            dp[i][1] = min(dp[i][1], dp[i-1][0] + 1)
        
        # 前一个位置已交换的情况
        if B[i-1] <= A[i] and A[i-1] <= B[i]:
            dp[i][0] = min(dp[i][0], dp[i-1][1])
        if B[i-1] <= B[i] and A[i-1] <= A[i]:
            dp[i][1] = min(dp[i][1], dp[i-1][1] + 1)
    
    res = min(dp[-1][0], dp[-1][1])
    # 如果结果还是INF，说明无法达成目标
    return res if res != INF else -1

# 测试示例
A = [1,8,12,11]
B = [7,3,10,15]
print(min_swap(A, B))  # 输出2

如果存在某个位置，无论交换与否都无法满足和前一个位置的升序要求，那么dp[i][0]和dp[i][1]都会保持INF，最终返回-1，表示无解。比如A=[3,2], B=[1,4]，无论怎么交换都无法让两个数组升序，函数会返回-1。

内容的提问来源于stack exchange，提问作者iamogbz