题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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
思路: 采用归并排序
分治的思想，将数组不断一分为二，直到数组中只有两个元素，统计逆序对个数。然后对相邻的两个子数组进行合并，由于已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组进行排序，避免在之后的统计过程中重复统计。在合并的时候也要计算组间的逆序对个数。
逆序对的总数 = 左边数组中的逆序对的数量 + 右边数组中逆序对的数量 + 左右结合成新的顺序数组时中出现的逆序对的数量
整个过程是一个归并排序的算法。
归并排序的性能不受输入数据的影响，时间复杂度始终都是
(a) 把长度为4的数组分解成两个长度为2的子数组；
(b) 把长度为2的数组分解成两个成都为1的子数组；
(c) 把长度为1的子数组 合并、排序并统计逆序对 ；
(d) 把长度为2的子数组合并、排序，并统计逆序对；
在上图（a）和（b）中，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组 排序 如上图（c）所示， 以免在以后的统计过程中再重复统计。
接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。
我们先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数，如下图（a）和（c）所示。如果第一个数组的数字小于或等于第二个数组中的数字，则不构成逆序对，如图b所示。每一次比较的时候，我们都把较大的数字从后面往前复制到一个辅助数组中，确保 辅助数组（记为copy） 中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。
python 实现：
# -*- coding:utf-8 -*-
class Solution:
def InversePairs(self, data):
# write code here
num, new_list = self.mergeSort(data)
return num%1000000007
def mergeSort(self, data):
# 逆序对个数
InversePairsNum = 0
# 归并过程
def merge(left,right):
# 合并时发现的逆序对个数
InversePairsNum = 0
result = [] # 保存归并后的结果
i = j = 0
while(i<len(left) and j<len(right)):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 当右边的元素被插入时，证明这个元素比左边的剩下的所有元素都小
# 可以组成len(left)-i个逆序对
InversePairsNum = InversePairsNum + (len(left)-i)
result = result + left[i:] + right[j:] # 剩余的元素直接添加到末尾,大概率是空的
return InversePairsNum, result
#
if len(data) <= 1:
return 0, data
else:
mid = len(data)//2 # //是向下取整
num_left, left = self.mergeSort(data[:mid])
num_right, right = self.mergeSort(data[mid:])
num_merge, new_list = merge(left, right)
InversePairsNum = num_left + num_right + num_merge
return InversePairsNum, new_list