分治策略求解“数组中的逆序对”你会了吗？
题目来源：Leetcode数组中的逆序对
一.题目在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
在看到题目的第一眼，我首先想到的是暴力法，直接利用一个二层循环，找到每个元素后面比它小的数即构成一个逆序对，但直到我看到限制中数组的长度最大可以到达50000，我立刻放弃了该想法，以我在Leetcode上刷题的经验，肯定会超时的。但我还是"作死"试了一下，果不其然：
像这种类似的题目，算法时间复杂度必定不能超过O(n2)O(n^2)O(n2)，于是又一个想法在我脑海中浮现——分治法，这道题的完全符合使用分治法的条件，将数组一分为二，分别在左右两个子数组中寻找逆序对，然后寻找左子数组中的元素和右子数组中的元素构成的逆序对，而且分治法的时间复杂度为O(nlogn)O(nlogn)O(nlogn)完全符合，这样一来算法思路就确定了，下面我将详细介绍如何利用分治法来求解该问题。
分治法求解的套路就不详细说了，无非就是分解，解决，合并，在本题中我直接套用了《算法导论》上归并排序的模板来求解该问题，在这里不得不来安利一波《算法导论》，博主也还在学习，欢迎大家一起来掉头发。
MERGE-SORT(A,p,r) //sort A[p..r]
if p < r
q = floor((p + r) / 2) //floor表示向下取整，即取不大于该数的最大整数
MERGE-SORT(A,p,q)
MERGE-SORT(A,q + 1,r)
MERGE(A,p,q,r)
2.2.1.2.归并函数
MERGE(A,p,q,r) //function：merge A[p..q] and A[q+1,r]
n1 = q - p + 1 //get the length of A[p..q]
n2 = r - q //get the length of A[q+1,r]
创建长度分别为n1 + 1,n2 + 1的数组L,R
L[0..n1 - 1] = A[p..q]#p到q的元素给L
R[0..n2 - 1] = A[q + 1.. r]#q+1到r的元素给R
L[n1] = infinity //infinity意为无穷大
R[n2] = infinity
i = 0
j = 0
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1
2.2.2.如何套用归并排序求解
对于两个已经排序的子数组，这里假设为[5,7]，[4,6]，进入归并函数后会在两个子数组后加上一个无穷大(Inifity)，这样左右子数组中的元素就都能弹出来：
由于，左右子数组都是有序的，当左子数组当前元素小于右子数组当前元素时，将做左子数组当前元素取出，这时我们已经可以找出左子数组当前元素构成的逆序对了，即用右子数组当前索引 - 右子数数字起始索引。为啥这样就可以了呢？理由很简单，归并过程中会不断取出左右子数组中较小的元素，而现在取的左子数组元素肯定比之前取出的右子数组元素要大。
示例求解过程Step0：起始状态
Step1：取出右子数组中的元素4放入结果数组
Step2：取出左子数组中的元素5放入结果数组，此时逆序对增加1(右子数组当前元素索引 - 右子数组起始索引 = 1)
Step3：取出右子数的元素6放于结果数组
Ste4：取出左子数组的元素7放在结果数组，逆序对增加2（有子数组当前索引 - 右子数组起始索引 = 2），此时原数组中的元素都遍历完了，本次寻找结束。
class Solution:
def reversePairs(self, nums: List[int]) -> int:
if nums == []:#输入为空
return 0
self.count = 0
self.divide(nums,0,len(nums) - 1)
return self.count
def merge(self,nums,start,mid,end):
#使用10000000000000000000000代表无穷大
L = nums[start:mid+1] + [10000000000000000000000]
R = nums[mid+1:end+1] + [10000000000000000000000]
i = j = 0
pos = start
for k in range(start,end+1):
if L[i] <= R[j]:
nums[pos] = L[i]
self.count += j
i += 1
else:
nums[pos] = R[j]
j += 1
pos += 1
def divide(self,nums,left,right):
if left == right:
return
else:
mid = (left + right) // 2
self.divide(nums,left,mid)
self.divide(nums,mid + 1,right)
self.merge(nums,left,mid,right)
要是觉得不错的话点个赞吧，码文不易，请多支持博主！！！
作者：斯曦巍峨