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

public class Solution {
    public int InversePairs(int [] array) {
        int len = array.length;
        if (len < 2) {
            return 0;
        }
        int[] temp = new int[len];
        return mergeSort(array, 0, len - 1, temp)%1000000007;
    }
    private int mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left >= right) {
            return 0;
        }
        int mid = left+(right - left) / 2;
        int leftPairs = mergeSort(nums, left, mid, temp);
        int rightPairs = mergeSort(nums, mid + 1, right, temp);
        if (nums[mid] <= nums[mid + 1]) {
            return (leftPairs + rightPairs);
        }
        int crossPairs = crossMergeSort(nums, left, right, temp, mid);
        return (leftPairs + rightPairs + crossPairs);
    }
    private int crossMergeSort(int[] nums, int left, int right, int[] temp,
                               int mid) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        int i = left;
        int j = mid + 1;
        int cnt=0;
        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            } else {
                //count = (count+(mid-i+1))%1000000007;
                cnt += (mid - i + 1);
                nums[k] = temp[j];
                j++;
                if(cnt>=1000000007){
                    cnt%=1000000007;
                }
            }
        }
        return cnt;
    }
}