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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public static long result = 0;
    private static int[] merge(int[] num1, int[] num2) {
        int res[] = new int[num1.length + num2.length];
        int k = 0, i = 0, j = 0;
        while (i < num1.length && j < num2.length) {
            if (num1[i] <= num2[j]) { //<= 算法稳定 否则排序不稳定
                res[k++] = num1[i++];
            } else {
                res[k++] = num2[j++];
                result += num1.length - i;
                result %=1000000007;
            }
        }
        if (i < num1.length) {
            while (i < num1.length) {
                res[k++] = num1[i++];
            }
        }
        if (j < num2.length) {
            while (j < num2.length) {
                res[k++] = num2[j++];
            }
        }
        return res;
    }
    public static int[] mergeSort(int[] num) {
        if (num.length <= 1)
            return num;
        int size1 = num.length / 2;
        int size2 = num.length - size1;
        int[] num1 = new int[size1];
        int[] num2 = new int[size2];
        int i;
        for (i = 0; i < size1; i++) {
            num1[i] = num[i];
        }
        for (int j = 0; i < num.length; i++, j++) {
            num2[j] = num[i];
        }
        return merge(mergeSort(num1), mergeSort(num2));


    }
    public int InversePairs (int[] nums) {
        // write code here
        mergeSort(nums);
        return (int)result;
    }
}