剑指：数组中的逆序对

import java.util.Arrays;

public class Solution {

     public static int InversePairs(int [] array) {
        if(array==null||array.length==0)
        {
            return 0;
        }
        
//        int[] copy = new int[array.length];
//        for(int i=0;i<array.length;i++)
//        {
//            copy[i] = array[i];
//        }
        int[] copy = Arrays.copyOf(array, array.length);
        int count = InversePairsCore(array,copy,0,array.length-1);//数值过大求余
        return count;   
     }

    private static int InversePairsCore(int[] array, int[] copy, int l, int r) {
        if(l==r){
            return 0;
        }
        int mid = l + ((r-l)>>1);
        int lCount = InversePairsCore(array,copy, l, mid)%1000000007;
        int rCount = InversePairsCore(array,copy, mid+1, r)%1000000007;
        int count = 0;
        int i=mid;
        int j=r;
        int locCopy = r;
        while(i>=l && j>mid){
            if(array[i]>array[j]){
                count += j-mid; //此注意边界
                copy[locCopy--] = array[i--];
                if(count>=1000000007)//数值过大求余
                {
                    count%=1000000007;
                }
            }else{
                copy[locCopy--] = array[j--];
            }
        }
        
        while(i>=l){
            copy[locCopy--] = array[i--];
        }
        while(j>mid){
            copy[locCopy] = array[j--];
        }
        
        for(int s=l; s<=r; s++){
            array[s] = copy[s];
        }
        
        return (lCount+rCount+count)%1000000007;
    }


    public static void main(String[] args) {
        int[] arr = {1,5,0,3,2};
        int res = InversePairs(arr);
        System.out.println(res);
    }
}