在数组中计数反转

Question

在数组中计数反转我正在设计一个算法来执行以下操作：给定的数组A[1... n]，为每一个i < j，找到所有的反转对，这样A[i] > A[j]..我使用合并排序和将数组A复制到数组B，然后比较这两个数组，但我很难了解如何使用它来找到倒置的数量。如有任何提示或帮助，将不胜感激。

Answer 1

这里是Java中的O(N Logn)解决方案。

long merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, count = 0;
    while (i < left.length || j < right.length) {
        if (i == left.length) {
            arr[i+j] = right[j];
            j++;
        } else if (j == right.length) {
            arr[i+j] = left[i];
            i++;
        } else if (left[i] <= right[j]) {
            arr[i+j] = left[i];
            i++;                
        } else {
            arr[i+j] = right[j];
            count += left.length-i;
            j++;
        }
    }
    return count;
}

long invCount(int[] arr) {
    if (arr.length < 2)
        return 0;

    int m = (arr.length + 1) / 2;
    int left[] = Arrays.copyOfRange(arr, 0, m);
    int right[] = Arrays.copyOfRange(arr, m, arr.length);

    return invCount(left) + invCount(right) + merge(arr, left, right);
}

这几乎是正常的合并排序，整个魔术隐藏在合并功能中。注意，当排序算法移除反转时。当合并算法计算被移除的倒置数时(有人可能会说)。

移除反转的唯一时刻是算法从数组的右侧提取元素并将其合并到主数组中。此操作移除的反转数是从要合并的左数组中留下的元素数。*)

希望有足够的解释。

Answer 2

我通过以下方法在O(n*log n)时间内找到了它。

1. 合并排序数组A并创建副本(数组B)

2. 取A[1]，通过二进制搜索在排序数组B中找到其位置。这个元素的倒置数将比它在B中位置的索引数少一个，因为在A的第一个元素后面出现的每一个较低的数都是一个反转。

   2A.累积反转的数目，以对抗变量num_inversion。

   2B.将A[1]从数组A及其在数组B中的相应位置移除

3. 从步骤2重新运行，直到A中没有更多的元素。

下面是这个算法的一个例子。原始阵列A=(6，9，1，14，8，12，3，2)

1：合并排序和复制到数组B

B=(1、2、3、6、8、9、12、14)

2：采用A[1]和二进制搜索在数组B中找到它

A[1]=6

B=(1，2，3，6, 8, 9, 12, 14)

6位于B阵列的第4位，因此有3处倒置。我们之所以知道这一点，是因为6位于数组A中的第一个位置，因此，随后出现在数组A中的任何较低值元素的索引都将为j>i(因为在本例中，I为1)。

2.b：从数组A中移除A[1]，也从数组B中的相应位置删除A[1](删除粗体元素)。

A=(6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)

B=(1，2，3，6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)

3：在新的A和B数组上重新运行步骤2。

A[1]=9

B=(1、2、3、8、9、12、14)

9现在位于阵列B的第5位，因此有4处倒置。我们之所以知道这一点，是因为9位于数组A中的第一个位置，因此随后出现的任何较低值元素的索引都将为j>i(因为在本例中，I再次为1)。将A[1]从数组A中移除，并从数组B中的相应位置删除A[1](删除粗体元素)

A=(9, 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)

B=(1，2，3，8，9, 12, 14) = (1, 2, 3, 8, 12, 14)

在循环完成后，继续这种方式将给出数组A的反转总数。

步骤1(合并排序)需要执行O(n*logn)。步骤2将执行n次，每次执行将执行一个二进制搜索，需要O(Logn)来运行总共O(n*logn)。因此，总运行时间为O(n*log n)+O(n*log n)=O(n*log n)。

谢谢你的帮助。在一张纸上写出样本数组确实有助于将问题可视化。

Answer 3

用Python

# O(n log n)

def count_inversion(lst):
    return merge_count_inversion(lst)[1]

def merge_count_inversion(lst):
    if len(lst) <= 1:
        return lst, 0
    middle = int( len(lst) / 2 )
    left, a = merge_count_inversion(lst[:middle])
    right, b = merge_count_inversion(lst[middle:])
    result, c = merge_count_split_inversion(left, right)
    return result, (a + b + c)

def merge_count_split_inversion(left, right):
    result = []
    count = 0
    i, j = 0, 0
    left_len = len(left)
    while i < left_len and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            count += left_len - i
            j += 1
    result += left[i:]
    result += right[j:]
    return result, count        


#test code
input_array_1 = []  #0
input_array_2 = [1] #0
input_array_3 = [1, 5]  #0
input_array_4 = [4, 1] #1
input_array_5 = [4, 1, 2, 3, 9] #3
input_array_6 = [4, 1, 3, 2, 9, 5]  #5
input_array_7 = [4, 1, 3, 2, 9, 1]  #8

print count_inversion(input_array_1)
print count_inversion(input_array_2)
print count_inversion(input_array_3)
print count_inversion(input_array_4)
print count_inversion(input_array_5)
print count_inversion(input_array_6)
print count_inversion(input_array_7)