九. sort 7 Reverse Pairs

这道题看着有些蹊跷，实际上就是针对mergesort出的题目。

1. if i < j and A[i] > A[j], 这和 merge_sort里面 if left[i] > right[j] 很相似，要知道 right 里的顺序是一定大于left的。
2. 对于sorted list： right and left，只要left[i] > right[j], 那么对于n>i, left[n]一定大于right[j]。
3. 基于以上两点，对mergesort算法修改一下，就可以实现。

class Solution:
    """
    @param A: an array
    @return: total of reverse pairs
    """
    def reversePairs(self, A):
        # write your code here
        def merge_sort(A, n):
            middle = len(A)//2
            if not middle:
                return A, n
            else:
                left, n = merge_sort(A[:middle], n)
                right, n = merge_sort(A[middle:], n)
           
            i = 0
            j = 0
            new_list = []
            while j < len(right) and i < len(left):
                if left[i] > right[j]:
                    new_list.append(right[j])
                    j += 1
                    n += len(left) - i
                else:
                    new_list.append(left[i])
                    i += 1
                    
            new_list.extend(left[i:])
            new_list.extend(right[j:])
            return new_list, n
            
        n = 0
        A, n = merge_sort(A, n)
        return n

注意：在这里用global n的话，好像编译通不过，但是本地测试是没有问题的。