leetcode51. 数组中的逆序对
问题描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
思路
1.暴力遍历：对每一个数和后面的数进行单独比较，符合条件+1，然后变量res记录个数，思路简单，代码如下
#双重循环版本
class Solution:
def reversePairs(self, nums: List[int]) -> int:
res = 0
for i in range(len(nums)-1):
for j in range(i,len(nums)):
if nums[i]>nums[j]:
res+=1
return res
#递归版本
class Solution:
def reversePairs(self, nums: List[int]) -> int:
if len(nums) i:
res+=1
return self.reversePairs(nums[1:])+res
两种版本，时间复杂度为O（n^2）,递归还可能超过最大递归层数，能用循环解决就不要递归了吧，虽然递归容易理解，run完后结果：
超出时间限制，其实也是意料之中，此题难度为困难，岂不是吾等渣渣能两分钟解决的。
2.归并排序：正常人确实挺难想到的，我是看了提示，往归并这方面想了，后面的逻辑确实是自己想的，归并的过程如下图所示：
归并的过程，不断从两个排序好的数组里，取数，用双指针法，如果左边大于右边，怎取右边值，知道两个数组指针都到最后了，得到一个新的排序好的数组，这个过程怎么计算出逆序的个数呢。
如7和5的归并过程，每次从右边数组取数的时候，我们需要记录左边数组还有多少个数，这些数都可以和右边取出来的数组成逆序对，因为这些数肯定都比它大。
再如[5,7] ,[4,6]的归并，通过4，5比较得知先取出4，左边数组还有2个值，即[5,4]，[5,7]都可以组成逆序对，然后5，6比较，取出5，不作操作；再比较6，7，取出6，因为从右边取值所以看左边数组大小为1，即[7,6]组成逆序对；
然后加上上面的[7,5]和[6,4]一共是五队逆序对，答案正确。思路有了，那代码如下，如果不熟悉归并排序过程的可能有点难理解吧，建议熟悉了归并排序后再看。
class Solution:
def __init__(self):
self.res = 0
def reversePairs(self, nums):
if nums:
self.sort(nums)
return self.res
def sort(self, nums):
l = 0
r = len(nums)-1
if l >= r:
return nums
else:
mid = (l+r)//2
left_nums = self.sort(nums[l:mid+1])
# print(left_nums)
right_nums = self.sort(nums[mid + 1:])
#print(right_nums)
res, res_num = self.merge(left_nums, right_nums)
print(res)
self.res += res
return res_num
def merge(self, l_nums, r_nums):
num = 0
new_nums = []
l_val = l_nums.pop(0)
r_val = r_nums.pop(0)
while True:
if l_val > r_val:
new_nums.append(r_val)
num += len(l_nums) + 1
if r_nums:
r_val = r_nums.pop(0)
else:
new_nums.append(l_val)
break
else:
new_nums.append(l_val)
if l_nums:
l_val = l_nums.pop(0)
else:
new_nums.append(r_val)
break
if l_nums:
new_nums.extend(l_nums)
if r_nums:
new_nums.extend(r_nums)
return num, new_nums
代码思路 主要框架用的是归并排序的写法，因为在后面需要统计逆序对的个数，所以无法采用原地归并，自己写一写就知道了，所以本文的归并排序是一个非本地的排序。
首先是用二分法实现排序的主体算法，主要的优化是在merge的过程，归并的过程，其他思路和归并一模一样，先全部拆分为长度为1的数组，然后进行归并，怎么统计逆序对的思路上面讲了，这个merge方法逻辑其实写的比较混乱，if-else用的有点多，建议感兴趣的可以重新写，这里的merge每次返回了一个num和res_num,num代表当前合并组成的逆序对个数，res_num代表返回归并好的有序数组，将每次返回的num加入到self.res变量,得到总的逆序对个数，其实是实例变量作为一个全局变量来使用，最后返回self.res即可。
另外大家一定要注意对边界值判断的问题，第一次在本地调通后，测试第十个案例的时候是个空数组，然后报了递归最大次数的错误，没有测试案例，还以为是python的最大递归次数只能999次造成的，然后设置了最大递归次数为50000，因为数组最长才50000加了这句：
import sys
sys.setrecursionlimit(1000000)
然而，并没什么用，依据第十个报错，看了看官方提供的python程序，一运行发现可以，明天这应该不是递归的问题，我的思路没什么问题，看了看测试案例为[],在前面加了个对[]的判断就ok了，白白瞎捣鼓半小时，菜是原罪呀。
作者：True | Fasle