题目

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

要求：空间复杂度 O(n)，工夫复杂度 O(nlogn)

输出: [7,5,6,4]返回值: 5输出：[1,2,3,4,5,6,7,0]返回值：7输出：[1,2,3]返回值：0

思路

最简略的思路是暴力求解，遍历数组每个元素，而后挨个和之后的元素比拟。这种做法工夫复杂度是O(n^2)。

最优思路是，利用归并排序的做法。
归并排序，将数组递归二分到子数组只有1个元素，而后向上排序合并。

只有左数组的某个元素，大于右数组的某个元素，那么左数组的该元素以及之后的所有元素，都能够和右数组的该元素造成逆序对。

因为下一层通过排序合并返回上一层后，上一层的左、右数组都是从小到大正序的，如果左数组的某个元素就比右数组的某个元素大，那么左数组的该元素前面的元素也必定比右数组的该元素大。

class Solution:    # 内部定义一个变量，用来记录逆序对数量    count = 0    def InversePairs(self, data):        def mergeSort(nums):            n = len(nums)            # 归并排序 递归完结条件 分到子数组长度为1不可分时递归完结            if n==1:                return nums            # 以后数组的两头地位            mid = n//2            # 左数组向下递归持续二分            left = mergeSort(nums[:mid])            # 右数组向下递归持续二分            right = mergeSort(nums[mid:])            # 定义两个指针: l、r，初始时别离指向左数组、右数组的开始            l = r = 0            # 定义一个变量，保留排序合并后的后果            tmp = []            # 当左、右两个数组 都没有遍历完            while l<=len(left)-1 and r<=len(right)-1:                # 如果左数组以后元素 <= 右数组以后元素                # 则没有逆序对，左数组元素退出到排序后果中，l指针挪动                if left[l] <= right[r]:                    tmp.append(left[l])                    l+=1                # 如果左数组以后元素 > 右数组以后元素                # 则左数组以后元素 以及 前面的所有元素，都大于右数组以后元素                # 都能够造成逆序对，count+这部分元素的数量                # 右数组以后元素退出到排序后果中，r指针挪动                else:                    tmp.append(right[r])                    self.count+=len(left[l:])                    r+=1            while l<=len(left)-1:                tmp.append(left[l])                l+=1            while r<=len(right)-1:                tmp.append(right[r])                r+=1            return tmp        mergeSort(data)        return self.count