题解 | 数组中的逆序对

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    """
    暴力超时
    """
    def InversePairs1(self , nums: List[int]) -> int:
        # write code here
        if not nums and len(nums)==1:
                return 0
        count=0
        n=len(nums)
        for i in range(n):
            
            for j in range(i,n):
                if nums[i]>nums[j]:
                    count+=1
        return  count 
    
    def InversePairs(self , nums: List[int]) -> int:
        if not nums or len(nums)<=1:
            return 0 
        def mergesort(left ,right):
            if left>=right:
                return 0
            mid =left+(right-left)//2
            # 递归
            count=mergesort(left,mid)+mergesort(mid+1,right)
            # 合并排序之后的两个数组
            i,j,temp=left,mid+1,[]
            while i<=mid and j<=right:
                if nums[i]<=nums[j]:
                    temp.append(nums[i])
                    i+=1
                else:
                    temp.append(nums[j])
                    j+=1
                    count+=mid-i+1 # 计算此时[i:mid] 这几个都是大于j 指向的数字
                    count=count %1000000007

            # 合并剩下的
            temp.extend(nums[i:mid+1])
            temp.extend(nums[j:right+1])
            #print(temp)
            nums[left:right+1]=temp
            return count 
        return  mergesort(0,len(nums)-1)  % 1000000007