题解 | 数组中的逆序对

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def InversePairs(self , nums: List[int]) -> int:
        # write code here
        # 定义内部归并排序函数（闭包形式）
        def merge_sort(arr, left, right):
            # 递归终止条件：子数组长度为0或1时逆序对为0
            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:
                    # 关键统计逻辑：当右元素较小时，左数组剩余元素都与arr[j]构成逆序对
                    temp.append(arr[j])
                    count += mid - i + 1  # 计算公式：(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)