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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @return int整型
#

class Solution:
    def InversePairs(self , data: List[int]) -> int:
        # write code here
        if not data:
            return 0
        mark = [x for x in data]
        res = [0]
        self.merge_sort(data,0,len(data)-1,res,mark)
#         print(data)
        return res[0]
    
    def merge_sort(self,data,left,right,res,mark):
#         print(left,right)
        if left>=right:
            return
        mid = int((left+right)/2)
        self.merge_sort(data, left, mid, res,mark)
        self.merge_sort(data, mid+1, right, res,mark)
        self.merge(data,left,mid,right,res,mark)
    
    def merge(self,data,left,mid,right,res,mark):
#         print(data,left,mid,right)
        k = left
        i,j = left,mid+1
        while i<=mid and j<=right:
            if data[i] > data[j]:
                res[0] += mid - i + 1
                mark[k] = data[j]
                j += 1
            else:
                mark[k] = data[i]
                i += 1
            k += 1
        while i<= mid:
            mark[k] = data[i]
            k += 1
            i += 1
        while j<=right:
            mark[k] = data[j]
            k += 1
            j += 1
        for i in range(left,right+1):
            data[i] = mark[i]
        res[0] %= 1000000007
#         print(data,left,mid,right)
#         print('------>')
#         data[left:right+1] = mark[left:right+1]