题目描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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

错误思路

自己做的时候一直想用dp的方法来做:用dp(i)表示以i开头的逆序对,然后在获得dp(j)(j=i-1)的时候,寻找序号大于j的第一个小于等于array(j)的序号i,dp(j) = dp(i)+if(array(i)<array(j)),但是这样的想法是不对的,用这样的动态规划转移方程式会漏掉一部分数据,因为在i之后可能会存在大于array(i)但小于array(j)的数,这部分数字和array(j)可以组成逆序对,但是却不会被计算在dp(j)中,所以这个思路是有问题的。

而且动态规划是用来求最值问题的方法,但是这道题目明显不是让我们求最大值和最小值的,从原则上来说,这种思路就是错误,一定要摒弃掉。

正确思路

所以不得已只能用大家提供的归并排序的思路来做这道题目以实现o(nlogn)的复杂度。
在归并排序的过程中 后一个数组的数如小于前一个数组的数,则一定能够构成逆序对且逆序对的数目可计算,因为待归并的两个数组提前已经归并排序过,所以不会出现像前面那样少统计或者多统计的情况出现。
思路:[A,B]中的逆序对=[A]的逆序对+[B]中的逆序对+将A,B混排在一起的逆序对
而将A,B混排在一起的逆序对求解看下面:

public