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

归并排序，在合并的时候加一句 countinverse += len(left)-l 计算逆序对的个数，最后返回左逆序对+本次逆序对+右逆序对的数量 【图源网络 侵删】

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @return int整型
#
class Solution:
    def InversePairs(self , data: List[int]) -> int:
        # write code here
        def mergesort(data):
            n = len(data)
            if n<=1:
                return data,0
            l,r = 0,0
            mid = n//2
            left,leftinverse = mergesort(data[:mid])
            right,rightinverse = mergesort(data[mid:])
            res = []#record ordered list
            countinverse = leftinverse+rightinverse
            while l < len(left) and r < len(right):
                if left[l]<=right[r]:
                    res.append(left[l])
                    l += 1
                else:
                    countinverse += len(left)-l
                    res.append(right[r])
                    r+=1
            res += left[l:]
            res += right[r:]
            return res,countinverse
        orderlist,count = mergesort(data)
        return count%1000000007