为什么要模1000000007 - CSDN博客
1000000007 是最小的十位质数。模1000000007，可以保证值永远在int的范围内。
题目描述：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
这道题在剑指offer中分析的很明白。解释比较多，就不贴在这里了。
另外参考逆序对计数问题 （python实现）
类似于归并排序（一个merge函数，传入两个排序好的子列表，返回一个合并的有序列表。一个递归函数，先把nums不断递归到底，然后再调用merge不断地逐层返回。）
这里，采用归并排序的思想。不过与归并排序有些微的不同。
Count函数：
传入两个参数两个有序子数列，
返回两个参数：一个合并好了的有序子数列，一个逆序对数（两个有序子序列直接拼接时，拥有的逆序对数）
函数的操作步骤如下图：
对上图的解释：
递归函数InversionNum：
类似于归并排序中的递归函数，不过稍微有些变化。
传入一个无序列表nums。返回一个有序列表，一个逆序对数。
注意，这里返回的逆序对数，不同于Count函数的操作方式：
- 由nums分成的两个子序列传入递归函数后，会返回的两个子序列内部的逆序对数count1和count2
- 对两个未排序的子序列调用Count函数，还会返回一个逆序对数count。
最终，递归函数返回的有序序列就是Count函数合并好的，而返回的逆序对数是nums一共拥有的逆序对数count1+count2+count.
若是不按照剑指offer的思路，单纯按照传统的归并排序的思路，从小到大不断构造新的序列，那么就看参考逆序对计数问题 （python实现），更容易接受。
这里的代码，不同于传统的归并排序，是按照从大到小的顺序合并两个子序列的，因此在while中的指针，以及在最后有一个子序列为空时应该怎么加上out，应该好好考虑一下。
代码实现：
# -*- coding:utf-8 -*-
class Solution:
def InversePairs(self, data):
def InversPairs_helper(data):
if len(data) <= 1:
return data,0
else:
mid = len(data) // 2
L_left,count1 = InversPairs_helper(data[:mid])
L_right,count2 = InversPairs_helper(data[mid:])
L_res,count = self.Count(L_left,L_right)
return L_res, count1 + count2 + count
L_res,count = InversPairs_helper(data)
return count
def Count(self,nums1, nums2):
# 构造一个列表，用来存储合并好了的序列
out = []
count = 0
p1 = len(nums1) - 1
p2 = len(nums2) - 1
# 开始合并
while p1 >= 0 and p2 >= 0:
# 若大于，说明存在逆序对数，更新count，更新指针
if nums1[p1] > nums2[p2]:
# 在out的前头添加nums1[p1]
out.insert(0, nums1[p1])
count = count + (p2 + 1)
p1 -= 1
# 若小于，说明不存在逆序对，不需要更新count，只更新指针即可
else:
# 在out的前头添加nums2[p2]
out.insert(0, nums2[p2])
p2 -= 1
# 当有一个列表为空时，把剩余的较小部分，从后往前加到out中
# 注意，此时，out应该在后面
# 注意，这里要加1
out = nums1[:p1 + 1] + out
out = nums2[:p2 + 1] + out
return out, count
S = Solution()
print(S.InversePairs([1,2,3,4,5,6,7,0]))
上面的代码思路，跟传统的归并排序思路差不多，先构造一个合并序列的函数，然后递归调用此函数即可。
但是，在牛客网上，不能通过。原因是Count中，对out序列用到了insert方法。这个列表方法的时间复杂度是O(n)。尽管后来改用参考中的传统的归并排序的方法，从小到大构造新序列，用时间复杂度为O(1)的append列表方法。还是超时了，只能通过75%。
最终看牛客上提交答案，该答案都是不再用列表方法构造新列表，而是在原有列表上直接修改列表。这样可以通过所有样例。（另外，我尝试着在上面代码的基础上，参考下面答案，只修改Count中的代码，用同样的方式构造out列表，但是还是不通过，个人觉得应该是在递归调用函数中，比较繁琐把。另外这也是Python比较慢的坑。）
参考代码：
这里的merge函数，直接传入一个data，此时并不用担心，修改data[k]以后，原有的data[k]就会消失了。因为这一点，巧妙的利用了递归的特性，此代码会先递归到底，得到left与right两个子序列，而data所有的元素都包含于这两个子序列中，因此data也是通过这两个子序列进行修改，因而不用担心值丢失的情况。
比如，对于[7,5,4,6]这个序列，会先递归进行到最后的[7],[5],[4],[6]的情况，再往上返回。比如倒数第二步中，此时left = [5,7],right = [4,6]，这时data = [7,5,4,6]。但是这时data是基于两个子序列修改的，所以不会丢失值。
代码实现：
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.count = 0
def InversePairs(self, data):
# write code here
data = self.merge(data)
return self.count % 1000000007
def merge(self, data):
n = len(data)
if n == 1:
return data
else:
mid = n // 2
left = self.merge(data[:mid])
right = self.merge(data[mid:])
i = len(left) - 1
j = len(right) - 1
k = len(left) + len(right) - 1
while i >= 0 and j >= 0:
if left[i] < right[j]:
data[k] = right[j]
j -= 1
else:
data[k] = left[i]
self.count += (j + 1)
i -= 1
k -= 1
while i >= 0:
data[k] = left[i]
i -= 1
k -= 1
while j >= 0:
data[k] = right[j]
j -= 1
k -= 1
return data
