[剑指Offer]数组中的逆序对

题目描述

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

解题思路

该题实为归并排序的衍生版,可查看归并排序

代码

Python(2.7.3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.count = 0

def InversePairs(self, data):
# write code here
self.mergeSort(data)
return self.count % 1000000007

def mergeSort(self, data):
def merge(left, right):
res = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
self.count += len(left[i:])
j += 1
return res + left[i:] + right[j:]
if len(data) <= 1:
return data
mid = len(data) // 2
left = self.mergeSort(data[:mid])
right = self.mergeSort(data[mid:])
return merge(left, right)