题目描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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
# -*- coding:utf-8 -*-
class Solution:
def InversePairs(self, data):
# write code here
res = [0]
def merge(a, aux, lo, mid, hi):
for i in range(lo, hi+1): aux[i]=a[i]
i, j = lo, mid+1
for k in range(lo, hi+1):
if i>mid:
a[k] = aux[j]
j += 1
elif j>hi:
a[k] = aux[i]
i += 1
res[0] += j-mid-1
elif aux[j]<aux[i]:
a[k] = aux[j]
j += 1
else:
a[k] = aux[i]
i += 1
res[0] += j-mid-1
def sort(a, aux, lo, hi):
if hi<=lo: return
mid = (lo+hi)//2
sort(a, aux, lo, mid)
sort(a, aux, mid+1, hi)
merge(a, aux, lo, mid, hi)
sort(data, [0]*len(data), 0, len(data)-1)
return res[0]%1000000007
网友评论