对两个数组进行排序所需的最小数量 "swaps"

Question

这是一个挑战问题，我一直在以最佳方式解决问题 (my attempt with failure analysis)。

给定两个长度相等的数组A = [1,8,12,11], B = [7,3,10,15]，仅通过交换对它们进行升序排序。

A swap 表示用相应的 B 元素替换 A 中索引 i 处的元素，反之亦然。

上面的例子可以用2 swaps解析为A = [1,3,12,15], B = [7,8,10,11]或A = [1,3,10,11], B = [7,8,12,15]。然而，在某些情况下，解决方案的交换次数不同，这里选择最小值，如果不可能，return -1

我将如何在 O(N) 中完美地解决这个问题？

Answer 1

令 f(i, swap) 表示可达到索引 i 的最小交换次数，其中 swap 是一个布尔值，表示索引 i 处的元素是否要交换.那么：

f(i, false) = min(
  f(i - 1, false) if A[i] >= A[i-1] and B[i] >= B[i-1] else Infinity,

  f(i - 1, true) if A[i] >= B[i-1] and B[i] >= A[i-1] else Infinity
)

f(i, true) = min(
  1 + f(i - 1, false) if B[i] >= A[i-1] and A[i] >= B[i-1] else Infinity,

  1 + f(i - 1, true) if B[i] >= B[i-1] and A[i] >= A[i-1] else Infinity
)

对两个数组进行排序所需的最小数量 "swaps"

Minimum number of "swaps" needed to sort two arrays

language-agnostic

arrays

sorting

algorithm

tuples