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

import java.util.*;


public class Solution {
    /*
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        // write code here
        return mergeSort(nums, 0, nums.length - 1);
    }

    public int merge(int[] num, int left, int mid, int right) {
        int tmpRight = mid;
        int tmpLeft = left;
        long reverseNum = 0;

        //计算逆序数
        while (tmpLeft < mid && tmpRight <= right) {
            if (num[tmpLeft] > num[tmpRight]) {
                //num[tmpLeft]满足条件的话，tmpLeft--mid中间（不包括边界）的元素也满足条件。取模防止溢出
                reverseNum+=(mid-tmpLeft) % 1000000007;
                tmpRight++;
            } else {
                tmpLeft++;
                
            }
        }
        //不需要合并直接返回 
        if(left >= right) return (int)reverseNum  % 1000000007;
        //合并
        int[] newNum = new int[right - left + 1];
        tmpLeft = left;
        tmpRight = mid;
        int index = 0;
        while (tmpLeft < mid && tmpRight <= right) {
            if (num[tmpLeft] < num[tmpRight]) {
                newNum[index] = num[tmpLeft];
                index++;
                tmpLeft++;
            }
            else {
                newNum[index] = num[tmpRight];
                tmpRight++;
                index++;
            }
        }
        //不需要继续比较大小，可以直接放入新数组的部分
        while(tmpLeft < mid) {
            newNum[index] = num[tmpLeft];
            tmpLeft++;
            index++; 
        }
        while(tmpRight <= right) {
            newNum[index] = num[tmpRight];
            tmpRight++;
            index++; 
        }
        index = 0;
        for(int i=left;i<=right;i++){
            num[i] = newNum[index];
            index++;
        }
        return (int)reverseNum  % 1000000007;
    }

    public int mergeSort(int[] num, int left, int right) {
        int mid = (right + left) / 2;
        int reverseNum = 0;
        if (left < right) {
            reverseNum += mergeSort(num, left, mid);
            reverseNum += mergeSort(num, mid + 1, right);
        }
        reverseNum += merge(num, left, mid + 1, right);
        return reverseNum % 1000000007;
    }
}