剑指offer -数组中的逆序对 - python
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
思路根据题目描述可知，逆序对指的是数组中前一个数字大于后一个数字的组合形式。因此，对于给定的数组来说，最为暴力的办法就是直接一个个进行比较，从头依次遍历找它后面比他小的元素个数，最后统计最终的结果。但是这样的方法的算法复杂度是O(n2)O(n^2)O(n2)，对于题目给定的数据范围肯定是无法在规定时间内完成的。
class Solution:
def InversePairs(self, data):
count = 0
a = data.copy()
a.sort()
for i in range(len(a)):
numbers = a[i:]
for n in numbers:
if data.index(n) < data.index(a[i]):
count += 1
return count % 1000000007
那么，如果将数组分化为小的数组，然后在小的数组上进行逆序对的寻找，那么算法的复杂度就会降到O(n∗logn)O(n* \log n)O(n∗logn)，这就需要归并排序。
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。
因此，我们可以使用归并排序进行数组的分解、排序和合并操作来降低算法复杂度，同时统计逆序对的数目。假设当前的测试示例为：[1，8，2，5，7，3][1，8，2，5，7，3][1，8，2，5，7，3]，那么使用归并排序的过程如下所示：
为了更好的理解在归并过程中归于逆序对的统计，我们将最后一步的归并过程单独拿出来看一下，如下所示：
当前的两个待归并的序列为[1,2,8][1,2,8][1,2,8]和[3,5,7][3,5,7 ][3,5,7]，设置leftleftleft和rightrightright指针分别指向两个序列的起始位置，并设置列表resresres保存合并后的元素，变量countcountcount保存逆序对数量。
leftleftleft = 1, rightrightright = 3，因为1 < 3 不构成逆序对，更新res=[1]res = [1]res=[1]，leftleftleft后移 leftleftleft = 2, rightrightright = 3，因为2 < 3不构成逆序对，更新res=[1,2]res = [1,2]res=[1,2]，leftleftleft后移 leftleftleft = 8, rightrightright= 3，因为 8 > 3，更新count=1count = 1count=1，res=[1,2,3]res = [1,2,3]res=[1,2,3]，rightrightright后移；8 > 5 ，更新count=2count = 2count=2，res=[1,2,3,5]res = [1,2,3,5]res=[1,2,3,5]，rightrightright后移；8 > 7，更新count=3count = 3count=3，res=[1,2,3,5,7]res = [1,2,3,5,7]res=[1,2,3,5,7]，共构成三个逆序对 更新res=[1,2,3,4,7,8]res = [1,2,3,4,7,8]res=[1,2,3,4,7,8]整个过程和一般的归并排序相同，核心之处在于需要在归并的过程中统计逆序对是否存在。
AC代码# -*- coding:utf-8 -*-
class Solution:
def InversePairs(self, data):
def merge(left, right):
count = 0
l = r = 0
result = []
while l < len(left) and r < len(right):
# 无法构成逆序对，left继续往后取元素比较，并将当前元素保存
if left[l] <= right[r]:
result.append(left[l])
l += 1
else:
# left[l]和right[r]可以构成逆序对，那么left[l:]中的元素必和right[r]构成逆序对
# 继续取right[r]之后的元素比较，并保存当前的right[r]
result.append(right[r])
r += 1
# 当右边的元素被插入时，证明这个元素比左边的剩下的所有元素都小
# 可以组成len(left)-l个逆序对
count += len(left) - l
# 保存剩下的元素
result += left[l:] + right[r:]
return count, result
def merge_sort(a_list):
l = 0
r = len(a_list)
mid = (l + r) // 2
count = 0
if len(a_list) <= 1:
return count, a_list
# 拆分
count_l, left = merge_sort(a_list[:mid])
count_r, right = merge_sort(a_list[mid:])
# 合并排序
count_merge, mergeData = merge(left, right)
count = count_l + count_r + count_merge
return count, mergeData
if data == None:
return None
count, result = merge_sort(data)
return count%1000000007
"""
# test
s = Solution()
a = [1,8,2,5,7,3]
print (s.InversePairs(a))
"""
作者：Forlogen
