题解 | 数组中的逆序对

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

            count = merge_sort(arr, left, mid) + merge_sort(arr, mid+1, right)

            count += merge(arr, left, mid, right)

            return count % 1000000007
        def merge(arr, left, mid, right):
            temp = []
            i, j = left, mid+1
            count = 0
            
            while i <= mid and j <= right:
                if arr[i] <= arr[j]:
                    temp.append(arr[i])
                    i += 1
                else:
                    temp.append(arr[j])
                    count += mid - i + 1
                    j += 1
            temp.extend(arr[i:mid+1])
            temp.extend(arr[j:right+1])
            arr[left:right+1] = temp
            return count
        return merge_sort(nums.copy(), 0, len(nums) -1)