题解 | 数组中的逆序对

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    private static final int MOD = 1000000007;

    public int InversePairs (int[] nums) {
        int count = 0;
        // write code here
        count = mergeAndSort(0, nums.length - 1, nums, new int[nums.length]);
        return count % MOD;
    }

    private int mergeAndSort(int left, int right, int[] arr, int[] tmp) {
        if (left >= right) {
            return 0;
        } 
        int mid = (left + right) / 2;
        int res = mergeAndSort(left, mid, arr, tmp) + mergeAndSort(mid + 1, right, arr, tmp);
        // 合并过程
        for (int i = left; i <= right; i++) {
            tmp[i] = arr[i];
        }
        int i = left;
        int j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                // 左边的已经处理完了，将右边的全部复制进去
                arr[k] = tmp[j++];
            } else if (j == right + 1) {
                arr[k] = tmp[i++];
            } else { 
                if (tmp[i] <= tmp[j]) {
                    arr[k] = tmp[i++];
                } else {
                    arr[k] = tmp[j++];
                    // 当 tmp[i] > tmp[j] 时，说明从 i 到 mid 的所有元素都和 tmp[j] 构成逆序对
                    res += mid - i + 1;
                    res %= MOD; // 防止结果溢出，对结果取模
                }
            }
        }
        return res;  
    } 
}

首先明白题目的意思，我理解错误了，[1,2,3,4,5,6,7,0]中不是1个逆序对(7,0)，而是有7个，1,0；2,0；3,0；4,0；5,0；6,0；7,0都是逆序对，不需要加仅仅挨在一起。

要求nlogn的话，肯定是一个递归排序。解题思路按照提示来的，使用归并排序的思想。我们写一个规定排序的过程，一个递归拆成2段，然后再合并。合并的时候有好几种情况，第一种情况，左边的完了，右边还没完，将右边的放进去就好了。另外一种情况，左边的还没完，右边的全完了，将左边的复制过去。第三种情况，两边正常进行中，如果左边的小于右边的，则复制左边的，指针挪一个，否则就移动右边的，并且将将指针往后挪一个。以上是规定排序的思想，想象一下，左边和右边都已经是有序了，这个时候如左边的比右边的大，说明了，左边的剩下的都比右边大。因此res= res + mid -i +1；至于为啥，我没想明白