35、数组中的逆序对

题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

输入例子:
1,2,3,4,5,6,7,0
输出例子:
7

这题就是归并排序，最后的结果超过了int的存储范围，所以要用long。

public class Solution {
    
    long count = 0;
    
    public int InversePairs(int [] array) {
        if(array.length==0){
            return 0;
        }
        int[] tmpArray = new int[array.length];
        mergeSort(array,tmpArray,0,array.length-1);
        return (int)(count%1000000007);
    }
    
    public void mergeSort(int [] array, int[] tmpArray, int start ,int end){
        if(start<end){
            int mid = (end - start)/2 + start;
            mergeSort(array, tmpArray, start, mid);
            mergeSort(array, tmpArray, mid+1, end);
            merge(array,tmpArray,start,mid,end);
        }
        
    }
    
    public void merge(int [] array, int[] tmpArray, int start, int mid, int end){
        int i=mid;
        int j=end;
        int k=end;
        //这里和标准merge实现略有不同    
        while(i>=start && j>=(mid+1)){
            if(array[i]>array[j]){
                count+=(j-mid);
                tmpArray[k]=array[i];
                i--;
            }else{
                tmpArray[k]=array[j];
                j--;
            }
            k--;
        }
        while(i>=start){
            tmpArray[k]=array[i];
            i--;
            k--;
        }
        while(j>=(mid+1)){
            tmpArray[k]=array[j];
            j--;
            k--;
        }
        System.arraycopy(tmpArray,start,array,start,end-start+1);
    }
}