题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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
思路
暴力法时间复杂度是o(n^2)，超时。
考虑一下，逆序是说a[i]>a[j]，i<j。那么在排序的过程中，会把a[i]和a[j]交换过来，这个交换的过程，每交换一次，就是一个逆序对的“正序”过程。
排序每个数，归并排序。
# 234 345
# 233445
def MergeElem(data, start, mid, end, temp): # data[start...mid], data[mid+1...end]
cnt = 0
i = start
j = mid + 1
k = start
while i <= mid and j <= end:
if data[j] < data[i]: # data[start...i...mid] data[mid+1...j...end]
temp[k] = data[j]
cnt += j - k
j += 1
k += 1
else:
temp[k] = data[i]
i += 1
k += 1
while i <= mid:
temp[k] = data[i]
i += 1
k += 1
while j <= end:
temp[k] = data[j]
j += 1
k += 1
data[start:end+1] = temp[start:end+1]
return cnt
def InverseCore(data, start, end, temp):
cnt = 0
if start < end:
mid = (start + end) // 2
cnt += InverseCore(data, start, mid, temp)
cnt += InverseCore(data, mid+1, end, temp)
cnt += MergeElem(data, start, mid, end, temp)
return cnt
def InversePairs(data):
# write code here
temp = data[:]
count = InverseCore(data, 0, len(data)-1, temp)
return count
print(InversePairs([1,2,3,5,4,6,7,0]))