数组中的逆序对

这道题的解法是使用归并排序，理解的关键在于两个区间，求两个区间之间的逆序对，与这两个区间内的数字是否有序无关，这样：

1. 自下而上的，先统计小的区间之间的逆序对；
2. 由小的区间合并成更大的区间之间的逆序对

public class Solution {
    private int count;
    public int InversePairs(int [] a) {
        if (a == null || a.length == 0) {
            return 0;
        }
        int[] tmp = new int[a.length];
        mergeSort(a, 0, a.length - 1, tmp);
        return count;
    }

    private void mergeSort(int[] a, int l, int r, int[] tmp) {
        if (l < r) {
            int m = (l + r) / 2;
            mergeSort(a, l, m, tmp);
            mergeSort(a, m + 1, r, tmp);
            merge(a, l, m, r, tmp);
        }
    }

    private void merge(int[] a, int l, int m, int r, int[] temp) {
        int k = 0, i = l, j = m + 1;
        while (i <= m && j <= r) {
            if(a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
                count += m - i + 1;
                count = count % 1000000007;
            }
        }
        while(i <= m) {
            temp[k++] = a[i++];
        }
        while(j <= r) {
            temp[k++] = a[j++];
        }
        for(i = 0; i < k; ++i) {
            a[l + i] = temp[i];
        }
    }
}

几个关键的点：

1. 每次对count增加新的计数之后，都要求模，否则可能数值过大
2. merge函数中，计算逆序对的值时用的是m - i + 1，思想是如果左区间的ai大于右区间的aj，那么从ai到am的每个数字都大于aj，但是思考一个问题，为什么这里不用j呢？因为是从右向左遍历右区间，因此如果我们想到：如果ai > aj，那么从a(m+1)到aj的每个数字都小于ai，这个时候一方面存在重复的计算，即计算ai和aj的时候，已经计算了a(j-1)了，但是这里还会重复计算一次；另一方面，由于合并的时候是一趟，因此ai处理后，那些比ai小的右区间中的数值已经被合并到了新的临时空间中了，因此ai右边的左区间中的剩下的值没有处理，又存在遗漏，因此这种算法是不正确的，所以只能使用i来计算。

总结起来这道题目并不简单，其中适用归并排序的点，和如何在归并排序中进行求解是理解本题的关键。