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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @return int整型
# 思路就是一个归并排序，只是过程中多了一个计算大小的个数
class Solution:
    def __init__(self) -> None:
        self.res = 0 # 这是目标逆序对数

    def merge(self, left, right): # 归并算法的合并过程
        i,j = 0, 0
        subL = []
        while i<len(left) and j<len(right):
            if left[i] < right[j]:
                subL.append(left[i])
                i += 1
            else:
                subL.append(right[j])
                j += 1
                self.res += len(left) - i # 如果左边大于右边，那必有逆序，且逆序数为从左边这一位开始到结尾的个数
        if i<len(left):
            subL += left[i:]
        if j < len(right):
            subL += right[j:]
        return subL

    def Div(self , data: List[int]): # 归并排序的划分阶段
        # write code here
        n = len(data)
        if n <= 1:
            return data
        mid = n//2
        left = self.Div(data[:mid])
        right = self.Div(data[mid:])
        return self.merge(left, right)

    def InversePairs(self , data: List[int]) -> int:
        _ = self.Div(data) # 归并过程，但是我们不需要他
        return self.res % 1000000007 # 只返回结果