题解 | 数组中的逆序对

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        // write code here
        if (nums == null || nums.length < 2) return 0;
        return (int) (mergeSort(nums, 0, nums.length - 1) % MOD);
    }
    private static final int MOD = 1000000007;
    private static long mergeSort(int[] nums, int l, int r) {
        if (l >= r) return 0;
        int mid = l + ((r - l) >> 1);
        long leftPairs = mergeSort(nums, l, mid), rightPairs = mergeSort(nums, mid + 1, r);
        int[] tmp = new int[r - l + 1];
        int pairs = 0, i = mid, j = r, k = tmp.length - 1;
        while (i >= l && j > mid) {
            if (nums[i] > nums[j]) {
                pairs += (j - mid);
                tmp[k--] = nums[i--];
            } else tmp[k--] = nums[j--];
        }
        while (i >= l) tmp[k--] = nums[i--];
        while (j > mid) tmp[k--] = nums[j--];
        for (k = 0; k < tmp.length; k++) nums[l + k] = tmp[k];
        return leftPairs + pairs + rightPairs;
    }
}