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

# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    MOD = 1000000007  # 定义常量
    # 事实上函数名应该小写
    def InversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        temp = [0 for i in range(n)]
        # 处理n个元素
        return self.merge_sort(nums, 0, n - 1, temp)

    def merge_sort(self, nums: List[int], low: int, high: int, temp: List[int]) -> int:
        mid = int((low + high) / 2)
        # 终止条件
        if low >= high:
            return 0
        # ！！！注意low, high是序号
        p = self.merge_sort(nums, low, mid, temp) + self.merge_sort(nums, mid + 1, high, temp)
        i, j = low, mid + 1
        # 建立相同数组
        for x in range(low, high + 1):
            temp[x] = nums[x]

        # 遍历数组
        for x in range(low, high + 1):
            # 若数组1全部插入，直接放入数组2数据
            if i == mid + 1:
                nums[x] = temp[j]
                j += 1

            # 若数组2全部插入，直接放入数组1数据
            elif j == high + 1:
                nums[x] = temp[i]
                i += 1

            else:
                if temp[i] <= temp[j]:  # 选择小的数组值插入
                    nums[x] = temp[i]
                    i += 1
                else:
                    nums[x] = temp[j]
                    j += 1
                    p += mid - i + 1

        return p % self.MOD

Day 1 2024.1.8

有点难，利用了归并排序解决问题，难点是首先要采用二路归并分化问题，其次是要理解通过有序数组的较小值小于给定值，那么其剩余值必然都小于给定值来减少比较次数，进行优化。