题解 | #数组中的逆序对#

public class Solution {
    public static final int MOD = 1000000007;
    int res;
    public int InversePairs(int [] array) {
        //进行归并排序，在merge的时候算一遍逆序对
        //merge的时候需要注意，逆序出现在右边小的时候，此时一次性算出右边这个数参与到的逆序对个数为leftN - left
        if(array==null||array.length<2) return 0;
        res = 0;
        mergeSort(array,0,array.length-1);
        return res;
    }
    public void mergeSort(int[] array,int l,int r){
        if(l<r){
            int mid = ((r-l)>>>1)+l;
            mergeSort(array,l,mid);
            mergeSort(array,mid+1,r);
            merge(array,l,mid,r);
        }
    }
    public void merge(int[] array,int l,int mid,int r){
        int N = r - l + 1;
        int[] help = new int[N];
        int left = l;
        int right = mid+1;
        int w = 0;
        while(left<=mid&&right<=r){
            if(array[left]<=array[right]){
                help[w++] = array[left++];
            }else{
                //右边小于的情况，抓逆序对
                res = (res + (mid - left + 1)) % MOD;
                help[w++] = array[right++];
            }
        }
        while(left<=mid){
            help[w++] = array[left++];
        }
        while(right<=r){
            help[w++] = array[right++];
        }
        //写回,此时w==N
        while(--w>=0){
            //注意加上l的偏移量
            array[w+l] = help[w];
        }
    }
}