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

借助归并排序，只在merge函数的第一个while循环里添加一个ans计数变量即可，其他的不用动。

• 因为当前左半段和右半段都是有序的，所以，如果arr[i]>arr[j]了，那么arr[i]到arr[mid]者几个数，都肯定比arr[j]大，所以这mid-i+1个数，都与arr[j]构成逆序数
• 因为检测到这个现象后会立马把arr[j]放在暂存数组的尾部，构成有序的数列，所以代码后续不会再运行到这个else片段里，也就不会出现重复计数的情况

public class Solution {
         int ans = 0;

    public  void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];

              // 如果使用ans+=(mid-i+1)%1000000007; 的写法，当遇到大规模输入时，会溢出
                ans=(ans+mid-i+1)%1000000007;
            }

        }
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 将temp中的元素全部拷贝到原数组中
        // 这个步骤是是需要重复多次的。先拷贝最小的串，越来越大，最后拷贝整个长串
        int t = 0;
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }
        public  void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 左边
            mergeSort(a, left, mid);
            // 右边
            mergeSort(a, mid + 1, right);
            // 左右归并
            merge(a, left, mid, right);
        }
    }
    public int InversePairs(int [] array) {
        mergeSort(array, 0, array.length - 1);
        return ans;
    }
}