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

from re import template
from heapq import merge
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    mod = 1000000007
    total = 0
    #归并实现
    def merge(self, li, low, mid, high):
        i,j = low,mid+1
        temp = []
        sum = 0
        #两边都有数
        while i<=mid and j<=high: 
            if li[i] < li[j]:
                temp.append(li[i])
                sum += (len(temp) - (i-low+1)) #i-low+1是当前的左列表入列个数
                i += 1
            else:
                temp.append(li[j])
                j += 1
        print(sum)
        #两边都没了
        while i<= mid:
            temp.append(li[i])
            sum += (len(temp) - (i-low+1))
            i += 1
            
        while j<= high:
            temp.append(li[j])
            j += 1
        li[low:high+1] = temp
        return sum

    #递归实现排序与计数
    def mergesort(self,li,low,high):
        if low < high:#至少两个元素
            mid = (low+high)//2
            self.mergesort(li,low,mid)
            self.mergesort(li,mid+1,high)#排序
            self.total += self.merge(li,low,mid,high)
            self.total %= self.mod

    def InversePairs(self, nums: List[int]):
        n = len(nums)
        self.mergesort(nums,0,n-1)
        return self.total
        
        

直接做归并排序，在归并的时候同时计数