数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数 P。并将 P 对 1000000007 取模的结果输出。 即输出 P % 1000000007

示例：

输入

1,2,3,4,5,6,7,0

输出

7

解题思路

通过归并排序的思想来求解，把数据分成前后两个数组（递归分到每个数组仅有一个数据项），合并时，如果前面的数组值 array[i] 大于后面数组值 array[j]，则前面 数组array[i] ~ array[mid] 都是大于array [j] 的，count += mid - i + 1

public class Solution {
    
    private int count = 0;
    
    public int InversePairs(int[] array) {
        if(array != null && array.length > 0) {
            mergeSort(array, new int[array.length], 0, array.length - 1);
        }
        return count;
    }
    
    public void merge(int[] array, int[] temp, int low, int mid, int high) {
        int i = low, j = mid + 1;
        int index = low;
        while (i <= mid && j <= high) {
            if (array[i] > array[j]) {
                count += mid - i + 1;
                temp[index++] = array[j++];
                if(count >= 1000000007) {
                    count %= 1000000007;
                }
            } else {
                temp[index++] = array[i++];
            }
        }
        while (i <= mid) {
            temp[index++] = array[i++];
        }
        while (j <= high) {
            temp[index++] = array[j++];
        }
        for(i = low; i <= high; i++) {
            array[i] = temp[i];
        }
    }
    
    public void mergeSort(int[] array, int[] temp, int low, int high) {
        if(low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        mergeSort(array, temp, low, mid);
        mergeSort(array, temp, mid + 1, high);
        merge(array, temp, low, mid, high);
    }
}