题解 | #数组中的逆序对#

该题最关键的是要想到逆序对的数量和对数组进行排序，调换元素位置的数量是一致的。举个例子[2,1,3,5,4]进行排序时，首先1,2要换一下位置，然后5,4要换一下位置，所以调换位置的数量是2，逆序数也是2.也就是说逆序对数量其实就是排序过程中调换位置的数量。所以只需要记录下排序过程中的位置调换数量就行了，排序算法刚好是O(nlogn)的，所以满足要求。

代码中我使用的归并排序。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @return int整型
#
class Solution:
    def InversePairs(self , data) -> int:
        # write code here
        # 逆序对的数量等于排序所需要花的调换位置数量
        self.count = 0
        self.mergesort(data)
        return self.count%1000000007

    def mergesort(self , data):
        if len(data) == 1 or len(data) == 0:
            return data
        else:
            mid = len(data)//2
            data1 = self.mergesort(data[0:mid])
            data2 = self.mergesort(data[mid:])
            p1 = 0 ; p2 = 0 
            new_data = []
            while p1<len(data1) or p2<len(data2):
                if p1 >= len(data1):
                    new_data.append(data2[p2])
                    p2+=1
                elif p2>=len(data2):
                    new_data.append(data1[p1])
                    p1+=1
                elif data1[p1]<data2[p2]:
                    new_data.append(data1[p1])
                    p1+=1
                else:
                    new_data.append(data2[p2])
                    self.count = self.count + len(data1)-p1
                    p2+=1
            return new_data

data = [1,2,3,4,5,6,7,0]
print(Solution().InversePairs(data))