剑指Offer(Python多种思路实现):数组中的逆序对
剑指Offer(Python多种思路实现):数组中的逆序对
面试51题：
题目：数组中的逆序对
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
解题思路一：
def InversePairs(self, data):
if len(data) i:
count += data.index(copy[i])
data.remove(copy[i])
i += 1
return count%1000000007
解题思路二：
#暴力法
def InversePairs2(self, data):
if len(data)data[j]:
count+=1
return count % 1000000007
解题思路三：
#归并排序法
def InversePairs3(self, data):
if len(data)=start and j>=start+length+1:
if data[i]>data[j]:
copy[indexCopy]=data[i]
indexCopy-=1
i-=1
count += j-start-length
else:
copy[indexCopy]=data[j]
indexCopy-=1
j-=1
#剩下一个数组未取完的操作：
while i>=start:
copy[indexCopy]=data[i]
indexCopy-=1
i-=1
while j>=start+length+1:
copy[indexCopy]=data[j]
indexCopy-=1
j-=1
return count+left+right
作者：雾行
