剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

• 0 <= 数组长度 <= 50000

Python 解答：
1.暴力超时

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        count = 0
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] > nums[j]:
                    count += 1
        return count

1.归并排序

class Solution:
    def reversePairs(self, nums: List[int]) -> int:

        def sort(nums, left, right):
            if left < right:
                mid = (left+right)//2
                sort(nums, left, mid)
                sort(nums, mid+1, right)
                merge(nums, left, mid, right)

        def merge(alist, left, mid, right):
            clist = [0 for i in range(right-left+1)]
            i, j, k = left, mid+1, 0
            while i <= mid and j <= right:
                if alist[i] <= alist[j]:
                    clist[k] = alist[i]
                    i += 1
                    k += 1
                elif alist[i] > alist[j]:
                    nonlocal count
                    count += mid-i+1
                    clist[k] = alist[j]
                    j += 1
                    k += 1
            while i <= mid:
                clist[k] = alist[i]
                i += 1
                k += 1
            while j <= right:
                clist[k] = alist[j]
                j += 1
                k += 1
            for i in range(len(clist)):
                alist[left+i] = clist[i]

        count = 0        
        sort(nums, 0, len(nums)-1)
        return count