1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

    int mod = 1000000007;

    long mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = left + ((right - left) >> 1);
        // 分治计算左右区间，并立即取模
        long res = (mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right)) % mod;
        
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
            // 严格判断nums[i] <= nums[j]，仅大于时统计逆序对
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
                // 累加后立即取模，防止溢出
                res = (res + mid - i + 1) % mod;
            }
        }
        // 拷贝左区间剩余元素
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        // 拷贝右区间剩余元素
        while (j <= right) {
            temp[k++] = nums[j++];
        }
        // 覆盖回原数组
        for (k = 0, i = left; k < temp.length; k++, i++) {
            nums[i] = temp[k];
        }
        return res;
    }

    public int InversePairs(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        return (int) (mergeSort(nums, 0, nums.length - 1) % mod);
    }