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

#


# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    result=0
    numbers=[]
    def InversePairs(self , nums: List[int]) -> int:
        # write code here

        self.numbers=nums.copy()
        self.tmp=nums.copy()
        self.cauculate(0,len(nums)-1)
        print(self.numbers)
        return self.result % 1000000007
    def cauculate(self,l,r):
         #只有一个的话不分
        if l>=r:
            return
        mid=l+int((r-l)/2)# mid归左边
       
        #分左边的
        self.cauculate(l,mid)
        #分右边的 返回一数组
        self.cauculate(mid+1,r)
        # 统计当前的有多少逆序
        # l mid ; mid+1 r 是有序的了
        i = l
        j=mid+1
        tag=l # 当前tmp指向
        # print(i,j)
        while(i<mid+1 and j<r+1):
            #print(i,j)
            if self.numbers[i]<self.numbers[j]:
                #顺序正确
                self.tmp[tag]=self.numbers[i]
                i+=1
                tag+=1
            else: # 顺序错误
                self.tmp[tag]=self.numbers[j]
                tag+=1
                j+=1
                # 加上tag到midle的所有数字
                self.result+=(mid-i+1)
        # 有可能有一边结束了 但另外一边没结束
        #
        while(i<mid+1  ):# and j==r
            self.tmp[tag]=self.numbers[i]
            i+=1
            tag+=1
        while(j<r+1 ): # and i==mid
            self.tmp[tag]=self.numbers[j]
            j+=1
            tag+=1
        for i in range(l,r+1):
            self.numbers[i]=self.tmp[i]



        # 两边分完了 把数组变为分完了的