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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
import math
class Solution:
    mod = 1000000007
    def merge_sort(self, start_index, end_index, nums):
        """
        
        """
        if start_index == end_index:
            return 0, [nums[start_index]]
        
        if (start_index + end_index) % 2 == 0:
            mid = int((start_index + end_index) / 2)
        else:
            mid = int((start_index + end_index + 1) / 2)

        # print("start, mid, end:",start_index, mid, end_index)

        if mid <= start_index + 1:
            res1 = 0
            nums1 = [nums[start_index]]
        else:
            res1, nums1 = self.merge_sort(start_index, mid, nums)
        
        # print("merge_sort input:", start_index, mid, nums)
        # print("merge_sort output:", res1, nums1)

        if mid + 1 >= end_index:
            res2 = 0
            nums2 = [nums[mid]]
        else:
            res2, nums2 = self.merge_sort(mid, end_index, nums)
        
        # print("merge_sort input:", mid, end_index, nums)
        # print("merge_sort output:", res2, nums2)

        res = (res1 + res2) % self.mod

        # print("res1:", res1, " res2:", res2)
        # print("nums1:", nums1, " num2:", nums2)

        new_nums = []

        if nums1[-1] < nums2[0]:
            new_nums = nums1
            new_nums.extend(nums2)
        elif nums2[-1] < nums1[0]:
            res += len(nums1) * len(nums2)
            new_nums = nums2
            new_nums.extend(nums1)
        else:
            nums1_len = len(nums1)
            i = 0

            nums2_len = len(nums2)
            j = 0

            while True:
                if nums1[i] < nums2[j]:
                    new_nums.append(nums1[i])
                    i += 1
                elif nums1[i] > nums2[j]:
                    res += nums1_len - i
                    new_nums.append(nums2[j])
                    j += 1

                if i >= nums1_len:
                    new_nums.extend(nums2[j:])
                    break

                if j >= nums2_len:
                    new_nums.extend(nums1[i:])
                    break

        return res % self.mod, new_nums


    def InversePairs(self , nums: List[int]) -> int:
        len_ = len(nums)
        res, new_nums = self.merge_sort(0, len_, nums)

        print("new_nums:", new_nums)

        return res % 1000000007