python--剑指offer--困难--51. 数组中的逆序对

from typing import List


class Solution:
    def sort(self, nums, tmp, l, r):
        mid = (l + r) // 2
        i, j, k = l, mid + 1, l
        cur_count = 0
        while i <= mid and j <= r:
            if nums[i] <= nums[j]:
                tmp[k] = nums[i]
                i += 1
                cur_count += (j - (mid + 1)) # 此处只能使用j,不能使用r
            else:
                tmp[k] = nums[j]
                j += 1
            k += 1

        for i in range(i, mid+1):
            tmp[k] = nums[i]
            k += 1
            cur_count += (j - (mid + 1))
        for j in range(j, r+1):
            tmp[k] = nums[j]
            k += 1

        nums[l:r+1] = tmp[l:r+1]
        return cur_count

    def mergeSort(self, nums, tmp, l, r):
        if l < r:
            mid = (l + r) // 2
            l_count = self.mergeSort(nums, tmp, l, mid)
            r_count = self.mergeSort(nums, tmp, mid+1, r)
            cur_count = self.sort(nums, tmp, l, r)
            return l_count + r_count + cur_count
        else:
            return 0

    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        tmp = [0] * n
        res = self.mergeSort(nums, tmp, 0, n - 1)
        print(nums)
        return res


if __name__ == '__main__':
    solution = Solution()
    nums = [7, 5, 6, 4]
    res = solution.reversePairs(nums)
    print(res)