【剑指offer】数组中的逆序对 python

【题目描述】

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

【思路】

最直接想到的是，进行冒泡排序，看交换的次数，但是这样的时间复杂度为O(n*n).为了降低时间复杂度，而且还要统计排序过程交换的次数，可以使用归并排序法，即是逐个比较，又不破坏前后关系，便于统计逆序对数。时间复杂度O(nlogn),空间复杂度为O(n),辅助数组的长度。

【代码】

python:
class Solution:
    def InversePairs(self, data):
        self.count=0
        if len(data)<2:return 0
        self.mergesort(data)
        return self.count%1000000007
    def mergesort(self,data):
        if len(data)<2:return data
        mid=len(data)>>1
        left=self.mergesort(data[:mid])
        right=self.mergesort(data[mid:])
        i,j=0,0
        merge=[]
        while i<len(left) and j<len(right):
            if left[i]<=right[j]:
                merge.append(left[i])
                i+=1
            else:
                merge.append(right[j])
                j+=1
                self.count+=len(left)-i
        return merge+left[i:]+right[j:]

通用的归并排序的代码如下：

class Solution:
    def InversePairs(self, data):
        if len(data)<2:return 0
        return self.mergesort(data)
    def mergesort(self,data):
        if len(data)<2:return data
        mid=len(data)>>1
        left=self.mergesort(data[:mid])
        right=self.mergesort(data[mid:])
        i,j=0,0
        merge=[]
        while i<len(left) and j<len(right):
            if left[i]<=right[j]:
                merge.append(left[i])
                i+=1
            else:
                merge.append(right[j])
                j+=1
        return merge+left[i:]+right[j:]