剑指offer_数组中的逆序对

题目描述

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

解题思路：

这题目在于测试用例数组超大，不能也不用取余输出啊。

首先想到排序，因为如果存在逆序对，在升序排序中，总要做点什么对吧。

因为数组超大，想到 递归、分治。快排？归并？堆排？

归并才是这题的真解，归并排序的改进，把数据分成前后两个数组(递归分到每个数组仅有一个数据项)，
合并数组，合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则前面数组array[i]~array[mid]都是大于array[j]的，count += mid+1 - i

注意：
这题目的数组超大，在记录返回值时候看，请使用float！！！每次返回之前先求余。。。（因为这问题，耽搁了许久。。。。坑）

上代码：

public class Solution {
    public int InversePairs(int [] array) {
        if(array==null||array.length==0){
            return -1;
        }
        int[] temp= new int[array.length];
        long res=getResult(array,temp,0,array.length-1);
        return (int)res%1000000007;
    }

    public long getResult(int[] array,int[] temp,int begin,int end){
        if(end<=begin){
            return 0;
        }
        int mid = (begin+end)/2;
        long left=getResult(array,temp,begin,mid);
        long right=getResult(array,temp,mid+1,end);
        long count= build(array,temp,begin,end);
        return count=(count+right+left)%1000000007;
    }

    public long build(int[] array,int[] temp,int begin,int end){
        int mid=(begin+end)/2;
        int i=begin;
        int j=mid+1;
        long count=0;
        int te=begin;
        while(i<=mid&&j<=end){
            if(array[i]<array[j]){
                temp[te++]=array[i++];
            }else{
                temp[te++]=array[j++];
                count+=(mid-i+1)%1000000007;
            }
        }
        while(i<=mid){
            temp[te++]=array[i++];
        }
        while(j<=end){
            temp[te++]=array[j++];
        }
        for(i=begin;i<=end;i++){
            array[i]=temp[i];
        }
        return count%1000000007;
    }
}