algorithm - 计算反转次数（从概念上讲？）

Question

总而言之，我试图了解我们如何准确地计算两个数组之间的反转次数。

例如，假设我们有以下两个数组：

A = [1, 2, 3, 4, 5, 6] B = [6, 3, 5, 4, 2, 1]

我将如何从概念上计算反转次数？也就是说，只看这两个数组，而忽略所涉及的编码。

另外，我知道在两个数组之间绘制线段的约定，但我试图在这里获得更深入的理解。

谢谢！

Answer 1

我不确定两个数组的多次反转是什么意思。

对于一个数组： 反转是一对 (a,b)，其中 a 在顺序上位于 b 之前，但 a > b。因此，从概念上讲，您可以尝试 B 的每一对。让我们从 6 开始，有 5 个反转：(6,3), (6,5), (6,4), (6,2), (6,1 ）。接下来是 3，只有 2 个：(3,2), (3,1)。以此类推，这里的结果是 13。

然而，这个算法非常幼稚并且运行 O(n^2)。更好的解决方案是基于归并排序算法，它在 O(n log n) 中运行。你可以在这里查看。我认为这仅适用于已排序的第一个数组。

对于两个数组：当涉及到 2 个数组时（再次从概念上讲），只需在 A 数组上方键入 B 数组并绘制连接相同元素的线。交叉的数量应该是反转的数量。这正是上面链接的基于合并排序的算法的工作原理。看看下面的图片：

结果还是13，所以这个方法确实有效。