计算数组中的反转 [英] Counting inversions in an array

问题描述

我正在设计一个算法来执行以下操作:给定数组 A[1... n]，对于每个 i <;j, 找出所有满足 A[i] >A[j].我正在使用归并排序并将数组 A 复制到数组 B，然后比较两个数组，但是我很难看到如何使用它来查找反转次数.任何提示或帮助将不胜感激.

I'm designing an algorithm to do the following: Given array A[1... n], for every i < j, find all inversion pairs such that A[i] > A[j]. I'm using merge sort and copying array A to array B and then comparing the two arrays, but I'm having a difficult time seeing how I can use this to find the number of inversions. Any hints or help would be greatly appreciated.

推荐答案

所以这里是 Java 中的 O(n log n) 解决方案.

So here is O(n log n) solution in java.

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);
}

这几乎是普通的归并排序，整个魔法都隐藏在归并函数中.请注意，排序算法会删除倒置.而合并算法会计算移除的倒置数(整理出来的人可能会说).

This is almost normal merge sort, the whole magic is hidden in merge function. Note that while sorting algorithm remove inversions. While merging algorithm counts number of removed inversions (sorted out one might say).

唯一移除反转的时刻是算法从数组的右侧获取元素并将其合并到主数组.此操作移除的反转数是要合并的左数组中剩余的元素数.:)

The only moment when inversions are removed is when algorithm takes element from the right side of an array and merge it to the main array. The number of inversions removed by this operation is the number of elements left from the the left array to be merged. :)

希望它足够解释.

这篇关于计算数组中的反转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！