排序两个数组所需的最小"交换"数

Question

这是一个挑战性的问题,我一直在解决最佳问题(我的失败分析尝试).

给定两个长度相等的数组,A = [1,8,12,11], B = [7,3,10,15]只需执行交换即可按升序对它们进行排序.

A swap表示将index iin A中的B元素替换为相应的元素,反之亦然.

上面的例子可以解决A = [1,3,12,15], B = [7,8,10,11]或A = [1,3,10,11], B = [7,8,12,15]两者兼而有之2 swaps.但是,在某些情况下,解决方案具有不同的交换次数,此处选择最小值,如果不可能,则返回-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
)