题目描述

blablabla

样例

class Solution(object):
    count = 0
    def inversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        self.merge(nums)
        return self.count


    def merge(self, nums):
        if len(nums) <= 1:
            return nums
        else:
            mid = len(nums) // 2
        left = self.merge(nums[:mid])
        right = self.merge(nums[mid:])
        return self.merge_sort(left, right)

    def merge_sort(self, a, b):
        la = len(a)
        lb = len(b)
        c = []
        a.append(float('inf'))
        b.append(float('inf'))
        i, j = 0, 0
        for x in range(0, la + lb):
            if a[i] < b[j]:
                c.append(a[i])
                i += 1
            else:
                c.append(b[j])
                j += 1
                self.count += la - i
        return c