数组中的逆序对
题目描述:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
知识点回顾:
思路:
思路1:
遍历每一个元素,让其与后面的元素对比,如果大于则count++,但是这样的时间复杂度是O(n2)。
思路2:用归并排序思路
例如7,5,4,6可以划分为两段7,5和4,6两个子数组
在7,5中求出逆序对,因为7大于5所以有1对
在6,4中求出逆序对,因为6大于4所以逆序对再加1,为2
对7,5和6,4进行排序,结果为5,7,和4,6
设置两个指针分别指向两个子数组中的最大值,p1指向7,p2指向6
比较p1和p2指向的值,如果大于p2,因为p2指向的是最大值,所以第二个子数组中有几个元素就有几对逆序对(当前有两个元素,逆序对加2,2+2=4),7>6,比较完之后将p1指向的值放入辅助数组里,辅助数组里现在有一个数字7,然后将p1向前移动一位指向5
再次判断p1和p2指向的值,p1小于p2,因为p1指向的是第一个子数组中最大值,所以子数组中没有能和当前p2指向的6构成逆序对的数,将p2指向的值放入辅助数组,并向前移动一位指向4,此时辅助数组内为6,7
继续判断p1(指向5)和p2(指向4),5>4,第二个子数组中只有一个数字,逆序对加1,4+1=5,为5对,然后将5放入辅助数组,第一个子数组遍历完毕,只剩下第二个子数组,当前只有一个4,将4也放入辅助数组,函数结束。辅助数组此时为4,5,6,7.逆序对为5.
Python实现:
# -*- coding:utf-8 -*-
class Solution:
def InversePairs(self, data):
# write code here
return self.inverseCount(data[:], 0, len(data)-1, data[:])%1000000007
def inverseCount(self, tmp, start, end, data):
if end-start <1:
return 0
if end - start == 1:
if data[start]<=data[end]:
return 0
else:
tmp[start], tmp[end] = data[end], data[start]
return 1
mid = (start+end)//2
cnt = self.inverseCount(data, start, mid, tmp) + self.inverseCount(data, mid+1, end, tmp)
# print(start, mid, end, cnt, data)
i = start
j = mid + 1
ind = start
while(i <= mid and j <= end):
if data[i] <= data[j]:
tmp[ind] = data[i]
i += 1
else:
tmp[ind] = data[j]
cnt += mid - i + 1
j += 1
ind += 1
while(i<=mid):
tmp[ind] = data[i]
i += 1
ind += 1
while(j<=end):
tmp[ind] = data[j]
j += 1
ind += 1
return cnt