计算 2 个数组之间的反转

Question

我正在寻找解决这个问题的算法：

给定 2 个数组 A 和 B，它们都是 [1..n] 的排列，请问这 2 个之间的反转次数是多少？

这里的反转是当一对元素 (i,j) 成立时：

if A.indexOf(i) > A.indexOf(j) && B.indexOf(i) < B.indexOf(j)

或

if A.indexOf(i) < A.indexOf(j) && B.indexOf(i) > B.indexOf(j)

我知道当您假设第一个数组已排序时，有多种方法可以执行此操作，例如在执行 MergeSort 时计算倒置，但我有 2 个未排序的数组。

示例：

A = [6,3,4,1,2,5] and B = [3,5,2,6,1,4]
No. of inversions = 9
6 has a lower index than 3 in A, but a higher index than 3 in B. This is an inversion.

我希望使用分而治之的方法在 O(n log n) 时间复杂度内实现这一目标。

Answer 1

这对你有用吗（虽然 O(N^2) 时间复杂度）：

        int[] A = ...;
        int[] B = ..;

        int count = 0;

        for (int i = 0; i < A.Length-1; i++) {
            for (int j = i+1; j < A.Length; j++) {
                if ((A[i] > A[j] && B[i] < B[j]) || (A[i] < A[j] && B[i] > B[j])) {
                    count++;
                }
            }
        }

Answer 2

为此，我们可以进行一个简单的替换（取自您的示例）： 6->1、3->2、4->3、1->4、2->5、5->6。因此，第一个列表变为 [1,2,3,4,5,6]，第二个变为 [2,6,5,1,4,3]。然后，我们可以运行一个简单的 O(n log n) 算法来计算第二个列表中的反转次数，从而给出答案。

可以使用附加索引列表在 O(n) 操作中完成此转换。 ind[i] 将是第一个列表中给定数字的索引，因此，如果 A[1]=6，则 ind[6]=1.

构造ind数组的代码：

    var A = new List<int> {6, 3, 4, 1, 2, 5};
    foreach (var num in A) Console.Write(num + " ");
    Console.WriteLine("");

    var indexes = new int[7];
    for (var i = 0; i < 6; ++i)
        indexes[A[i]] = i + 1;

    for (var i = 1; i < 7; ++i) Console.Write(indexes[i] + " ");
    Console.WriteLine("");

然后，给定这个数组（在本例中为 [4,5,2,3,6,1]），我们可以使用 resultArray[i] = ind[B[i]] 进行替换；

构造替换数组的代码：

    var B = new List<int> {3, 5, 2, 6, 1, 4};

    var resultList = new List<int>();
    for (var i = 0; i < 6; ++i)
        resultList.Add(indexes[B[i]]);

    for(var i = 0; i < 6; ++i)
        Console.Write(resultList[i] + " ");

然后我们可以运行计算最后一个数组中的排列的算法，这将是答案。（我可以在 O(n log n) 中给出计算排列的代码，但我认为这不是这里的问题）。

计算 2 个数组之间的反转

Counting Inversions between 2 arrays

algorithm

mergesort

divide-and-conquer