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

public class Solution {
    /*
      解题思路：
        借助归并排序的方法，在子问题进行合并的时候统计逆序对的个数
     */
    public int InversePairs(int [] array) {
        int len = array.length;
        if (len == 0) return 0;
        // 分治法
        int[] temp = new int[len];
        return mergeSort(array, 0, len - 1, temp);
    }
    // 分治排序
    private int mergeSort(int[] arr, int left, int right, int[] temp) {
        // 二分法
        if (left >= right) return 0;
        int mid = (left + right) / 2;
        int res = mergeSort(arr, left, mid, temp) + mergeSort(arr, mid + 1, right,
                  temp);
        // 取模运算
        final int mod = 1000000007;
        res %= mod;
        // 合并排序
        int i = left;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) temp[index++] = arr[i++];
            else {
                temp[index++] = arr[j++];
                res += mid - i + 1; // 统计逆序对
            }
        }
        while (i <= mid) temp[index++] = arr[i++];
        while (j <= right) temp[index++] = arr[j++];
        if (right - left + 1 >= 0)
            System.arraycopy(temp, 0, arr, left, right - left + 1);
        return res % mod;
    }
}