题解 | #数组中的逆序对#

import java.util.*;


public class Solution {
    int count = 0;
    public int InversePairs(int [] array) {
        // 长度小于2则无逆序对
        if (array.length < 2)
            return 0;
        // 进入归并
        mergeSort(array, 0, array.length - 1);
        return count;
    }

    public void mergeSort(int[] array, int left, int right) {
        // 找分割点
        int mid = left + (right - left) / 2;
        if (left < right) {
            // 左子数组
            mergeSort(array, left, mid);
            // 右子数组
            mergeSort(array, mid + 1, right);
            // 并
            merge(array, left, mid, right);
        }
    }

    public void merge(int[] array, int left, int mid, int right) {
        // 创建临时数组，长度为此时两个子数组加起来的长度
        int[] arr =  new int[right - left + 1];
        // 临时数组的下标起点
        int c = 0;
        // 保存在原数组的起点下标值
        int s = left;
        // 左子数组的起始指针
        int l = left;
        // 右子数组的起始指针
        int r = mid + 1;
        while (l <= mid && r <= right ) {
            // 当左子数组的当前元素小的时候，跳过，无逆序对
            if (array[l] <= array[r]) {
                // 放入临时数组
                arr[c] = array[l];
                // 临时数组下标+1
                c++;
                // 左子数组指针右移
                l++;
            } else { // 否则，此时存在逆序对
                // 放入临时数组
                arr[c] = array[r];
                // 逆序对的个数为    左子数组的终点- 当前左子数组的当前指针
                count += mid + 1 - l;
                count %= 1000000007;
                // 临时数组+1
                c++;
                // 右子数组的指针右移
                r++;
            }
        }

        // 左子数组还有元素时，全部放入临时数组
        while (l <= mid)
            arr[c++] = array[l++];
        // 右子数组还有元素时，全部放入临时数组
        while (r <= right)
            arr[c++] = array[r++];
        // 将临时数组中的元素放入到原数组的指定位置
        for (int num : arr) {
            array[s++] = num;
        }
    }
}

这道题中有三个晦涩的地方：

1，使用归并排序，求出逆序方法，要用到递归的思想

2，在合并临时数组的时候，如果左数组的当前值大于了右数组的当前值，那么左数组余下的个数就是逆序数，因为左数组已经是升序的了

3，在循环中不断count %= 1e9+7, 也就是count %= 1000000007时，最后跟一次性count %= 1000000007是一样的

很多人在3这点卡住，但我想了一个“辣条包装生产线”的例子，希望能帮到大家：

首先要明白，做count %= 1e9+7是为了把一个很大的数限制在int类型的范围内，在这里count是数组里的逆序数，当数组很大很复杂时，这个数可能非常大，所以要这么处理，在这里也是为了教会我们这个可以用在以后代码里的小trick。

为了理解它，我们开始打个比方。count += mid + 1 - l 是用来计算出逆序数并且累加的，这就像是一个不断地产生辣条的机器，而产出的辣条会累积起来放在count里。然后我们规定每一包里要装1e9+7根辣条，这就相当于 count %= 1e9+7，如果我们最后剩下来的不足1e9+7根，也就是不够一包，那么我们就把剩余的放回count里，也就是等待下一批做好的辣条，然后混在一起继续包装（下一个循环）。

在现实中，这个跟一次性把所有的原料都做成辣条（对应把整个数组的逆序数算出来），然后再一次性包装count %= 1e9+7（对应P mod 1000000007）实质上是一样的，最后都会剩下一样多的辣条存在count里。而关键就在java里，count作为一个int类型的数据，大小是有限制的，辣条并不能无限地堆放在count里，如果在生产的过程中（计算整个数组的逆序数的过程中）累加的count超过了int的限制，那么就会因为溢出而导致最后答案出错，而如果把count %= 1e9+7放在循环里，就相当于在一边生产一边包装，不断给新生产的辣条（逆序数）腾出地方，保证了最后答案的正确性。