每日leetcode——JZ51 数组中的逆序对数据结构与算法

题目在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
要求：空间复杂度 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个元素，然后向上排序合并。
【每日leetcode——JZ51 数组中的逆序对】只要左数组的某个元素，大于右数组的某个元素，那么左数组的该元素以及之后的所有元素，都可以和右数组的该元素形成逆序对。
因为下一层经过排序合并返回上一层后，上一层的左、右数组都是从小到大正序的，如果左数组的某个元素就比右数组的某个元素大，那么左数组的该元素后面的元素也肯定比右数组的该元素大。

class Solution: # 外部定义一个变量，用来记录逆序对数量 count = 0def 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 tmpmergeSort(data) return self.count