数组中的逆序对

题目描述

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

public class Solution {
    private long sum;
    public int InversePairs(int [] array) {
        sum=0;
        int l=0;
        int r=array.length-1;
        divide(l,r,array);
        return (int)(sum%1000000007);
    }
    
    //归并排序
    private void divide(int l,int r,int[] array){
        if(l!=r){
            int mid=(l+r)>>1;
            divide(l,mid,array);
            divide(mid+1,r,array);
            merge(l,r,mid,array);
        }
    }
    
    private void merge(int l,int r,int mid,int[] array){
        int i=l;//左区间起点
        int j=mid+1;//右区间起点
        int[] temp=new int[r-l+1];
        int index=0;
        while(i<=mid && j<=r){
            if(array[i]>array[j]){
                temp[index++]=array[j++];
                sum+=mid-i+1;  //核心，用于逆序对计数
            }else{
                temp[index++]=array[i++];
            }
        }
        
        while(i<=mid){
            temp[index++]=array[i++];
        }
        while(j<=r){
            temp[index++]=array[j++];
        }
        index=0;
        for(int k=l;k<=r;k++){
            array[k]=temp[index++];
        }
    }
}