题解 | 数组中的逆序对

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param nums int整型一维数组 
     * @return int整型
     */
    private int merge_sort(int[] nums, int l, int r, int[] s) {
        if (l >= r) return 0;
        int mid = l + r >> 1;
        int ans = 0;
        ans += merge_sort(nums, l, mid, s) + merge_sort(nums, mid + 1, r, s);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                s[k++] = nums[i++];
            } else {
                ans += mid - i + 1;
                ans %= 1000000007;
                s[k++] = nums[j++];
            }
        }
        while (i <= mid) s[k++] = nums[i++];
        while (j <= r) s[k++] = nums[j++];
        for (int m = l, n = 0; m <= r; m++, n++) nums[m] = s[n];
        return ans;
    }

    public int InversePairs(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] s = new int[nums.length];
        return merge_sort(nums, 0, nums.length - 1, s);
    }
}