题解 | #数组中的逆序对# 解释下答案

思路是分治快速排序,右边数组的值小于左边,则左边数组所有值都大于右边这个值,累加至总计逆序中

import copy
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def InversePairs(self , nums: List[int]) -> int:
        # write code here
        n = len(nums)
        _nums = [0 for i in range(n)]

        return self.run(0, len(nums) - 1, nums, _nums)

    
    # 二分左闭右闭 [l,r] ,_nums是临时记录的中间数组,因为copy需要时间长所以放到参数中,只替换需要用的部分值
    def run(self, l, r, nums, _nums):
        if l >= r:
            return 0

        m = (l + r) // 2
        # 先二分取最小单元
        res = self.run(l, m, nums, _nums) + self.run(m + 1, r, nums, _nums)

        # 排序开始,先定义临时列表存储当前的列表状态
        for k in range(l, r+1):
            _nums[k] = nums[k]

        # 定义二分法左右两个数组的起始的下标
        i, j = l, m + 1
        # 循环整个列表长度的次数
        for k in range(l, r + 1):
            # 一边的数组都排序完了就依次把另一边的替换到nums
            if i == m + 1:
                nums[k] = _nums[j]
                j += 1
                continue
            elif j == r + 1:
                nums[k] = _nums[i]
                i += 1
                continue

            # 将较小的值依次替换到nums
            if _nums[i] < _nums[j]:
                nums[k] = _nums[i]
                i += 1
            else:
                nums[k] = _nums[j]
                j += 1
                # 左边数组的所有值都小于右边数组的_nums[j],所以累加上左边数组的剩余长度就行
                res += m - i + 1

        return res % 1000000007