51 数组中的逆序对

牛客

描述

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

分治，类似 merge sort ，在合并的时候，左边的如果比右边某个数字大，则比右边那个数字前面的都大。时间复杂度 o(log n)

public class Solution {
    public int InversePairs(int [] array) {
        long res = merge(array,0, array.length-1);
        return (int) (res%1000000007);
    }
    
    private long merge(int[] array, int begin, int end){
        if(begin>=end) return 0;
        
        int mid = (begin+end)/2;
        
        long left = merge(array, begin, mid);
        long right = merge(array, mid+1, end);
        long count = 0;
        
        int[] arr = new int[end-begin+1];
        int index = 0;
        for(int i=begin;i<=end;++i){
            arr[index++] = array[i];
        }
        
        int i1 = mid-begin, i2=arr.length-1;
        index = end;
        
        while(i1>=0 && i2>=mid-begin+1){
            if(arr[i1]>arr[i2]){
                count+=i2-(mid-begin);
                array[index--] = arr[i1--];
            } else {
                array[index--] = arr[i2--];
            }
        }
        
        while(i1>=0){
            array[index--]=arr[i1--];
        }
        
        while(i2>=mid-begin+1){
            array[index--]=arr[i2--];
        }
        
        
        return count+left+right;
    }
}