题解 | #数组中的逆序对# 归并排序思想

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

        ans = 0
        MOD = 1000000007

        # write code here
        def merge_sort(arr):
            if len(arr) <= 1:
                return arr

            mid = len(arr) // 2
            s1 = merge_sort(arr[:mid])
            s2 = merge_sort(arr[mid:])
            return merge(s1, s2)

        def merge(s1, s2):
            res = []
            i = j = 0
            while i < len(s1) and j < len(s2):
                if s1[i] <= s2[j]:
                    res.append(s1[i])
                    i += 1
                else:
                    res.append(s2[j])
                    nonlocal ans
                    ans = (ans + len(s1) - i) % MOD
                    j += 1
            res.extend(s1[i:])
            res.extend(s2[j:])
            return res
        merge_sort(nums)
        return ans