逆序数求解算法

逆序数

数组中逆序对的个数

逆序对：从数组随机取两个元素arr[i], arr[j]， 其中i < j 如果arr[i] > arr[j]，则形成一个逆序对。

逆序数可以衡量一个数组的有序程度，逆序数越大，说明数组的递增性越差，如果逆序数为0，说明数组是严格递增的，如果为 $C_n^2$，则数组是严格递减的。

1. 暴力算法

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

这种时间复杂度下，1s 的限制只能跑n = 1000 的数据规模

public int getInverse(int[] arr){
    int n = arr.length, res = 0;
    for(int i = 0; i < n; i ++){
        for(int j = i + 1; j < n; j ++){
            if(arr[i] > arr[j]){
                res ++;
            }
        }
    }
    return res;
}

2. 归并算法

对于一个数组arr=[5, 3, 7, 6, 4] 它的逆序数是 5，分别是(5, 3), (5, 4), (7, 6), (7, 4), (6, 4)。将数组从中间分成两部分a = [5, 3, 7] b = [6, 4] 。其中a 的逆序数为1， (5, 3) ,b 的逆序数为1，(6, 4) ，a 与 b 之间的逆序数为3， (5, 4) , (7, 6), (7, 4)。我们可以发现arr 的逆序数等于这三部分之和。

因此我们只要求出这三部分的逆序数就可以了，首先如何求数组内的逆序数？很简单，a 可以继续像arr 一样分成两部分递归求解即可。这是分治的思想。

递归求解完a b 的逆序数之后，如何求解两者之间的逆序数呢？

我们进一步观察子数组，子数组的元素位置发生变化其实不会改变数组之间的逆序数的。比如将a 变成[7, 5, 3],将b 变成[4, 6] ，他们之间的逆序数还是 3。

而如果两个子数组有序的话，就很容易能求出子数组之间的逆序数。因此我们在求完子数组的逆序数时，还要对数组进行排序。以更方便的求子数组之间的逆序数。

其实上面的过程先分治，再合并排序的过程，就是归并排序的思想。只不过在归并的时候计算子数组之间的逆序数。

如何计算呢：比如两个子数组a = [3,8, 9] 和 b = [1, 2, 7] 要合并。

首先b[0] < a[0] 所以1 会对3 产生一个逆序数，而因为数组是有序的，因此a[0] - a[2] 都比b[0] 大，所以1一共会产生3个逆序数。

按照上述方式，依次求出b[i] 产生的逆序数的，累加结果即可。

时间复杂度：$nlog(N)$

空间复杂度：$O(n)$

// 求解数组 arr 的逆序数 
public static int merge(int[] arr, int left, int right){
        if(left >= right){
            return 0;
        }
        int mid = (right + left) >> 1;
        // 递归计算每个子数组内部的逆序数
        int left_inverse = merge(arr, left, mid);
        int right_inverse = merge(arr, mid + 1, right);

        // 合并，求左半边数组对右半边数组产生的逆序数，
        int res = 0;
        // 存放两个子数组合并后结果的临时数组
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right){
            if(arr[i] <= arr[j]){
                temp[k ++] = arr[i ++];
            }else {
                // arr[j] 对区间 [i , mid] 都产生一个逆序数
                res += mid - i + 1;
                temp[k ++] = arr[j ++];
            }
        }
        while (i <= mid){
            temp[k ++] = arr[i ++];
        }
        while (j <= right){
            temp[k ++] = arr[j ++];
        }
        for (int m = 0; m < temp.length; m ++){
            arr[left + m] = temp[m];
        }
		// 返回三部分逆序数之和
        return res + left_inverse + right_inverse;
    }