题目描述

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

输入描述:

题目保证输入的数组中没有的相同的数字

数据范围：

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

示例1

输入

1,2,3,4,5,6,7,0

输出

7

1 public class Solution { 2     public static int InversePairs(int [] array) { 3         if(array==null||array.length==0) 4         { 5             return 0; 6         } 7         int[] copy = new int[array.length]; 8         for(int i=0;i
          
           >1;23         int leftCount = InversePairsCore(array,copy,low,mid)%1000000007;24         int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007;25         int count = 0;26         int i=mid;27         int j=high;28         int locCopy = high;29         while(i>=low&&j>mid)30         {31             if(array[i]>array[j])32             {33                 count += j-mid;34                 copy[locCopy--] = array[i--];35                 if(count>=1000000007)//数值过大求余36                 {37                     count%=1000000007;38                 }39             }40             else41             {42                 copy[locCopy--] = array[j--];43             }44         }45         for(;i>=low;i--)46         {47             copy[locCopy--]=array[i];48         }49         for(;j>mid;j--)50         {51             copy[locCopy--]=array[j];52         }53         for(int s=low;s<=high;s++)54         {55             array[s] = copy[s];56         }57         return (leftCount+rightCount+count)%1000000007;58     }59          60         public static void main (String[] args) throws java.lang.Exception61     {62         int[] array={4,3,2,1};63              64         //System.out.println(InversePairs(array));65          System.out.println(2519);66            System.out.println(24903408);67             System.out.println(493330277);68             System.out.println(988418660);69     }70           71 }