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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def InversePairs(self , nums: List[int]) -> int:
        # write code here
        if not nums:
            return 0
         
        count = 0  # 定义一个全局变量 count，用于记录逆序对的数量。
        tmp = [0] * len(nums)
         
        def mergeSort(nums, start, end):
		"""
        用于拆分和排序原始数组：
        1.递归终止条件是当子数组长度小于等于 1 时。
        2.将原始数组拆分为两个子数组，分别进行递归排序。
        3.调用辅助函数 merge，合并排序好的两个子数组。
        """
            if start >= end:
                return
             
            mid = (start + end) // 2
            mergeSort(nums, start, mid)
            mergeSort(nums, mid+1, end)
            merge(nums, start, mid, end)
         
        def merge(nums, start, mid, end):
		"""
        用于合并排序好的两个子数组并计算逆序对的数量：
        1.在合并过程中，利用左右两个子数组已排好序的特点：
            1.初始化指针 i 和 j 分别指向左子数组和右子数组的起始位置。
            2.如果左子数组中的元素nums[i]大于右子数组中的元素nums[j]，则说明右子数组中的元素都小于nums[i]，形成逆序对。
            3.统计逆序对的数量：count += mid - i + 1，其中 mid 是左子数组的长度，也是索引为 mid 的元素所在的位置。
            4.将较小的元素放入辅助数组，并向后移动对应的指针。
        2.重复上述步骤，直到其中一个子数组遍历完毕。
        3.将剩余的子数组中的元素放入辅助数组。
        """
            nonlocal count
            i, j = start, mid+1
            k = start
             
            while i <= mid and j <= end:
                if nums[i] <= nums[j]:
                    tmp[k] = nums[i]
                    i += 1
                else:
                    tmp[k] = nums[j]
                    count += mid - i + 1
                    j += 1
                k += 1
             
            while i <= mid:
                tmp[k] = nums[i]
                i += 1
                k += 1
             
            while j <= end:
                tmp[k] = nums[j]
                j += 1
                k += 1
             
            for i in range(start, end+1):
                nums[i] = tmp[i]
         
        mergeSort(nums, 0, len(nums)-1)
         
        return count % 1000000007