需求描述
数组中的两个数字，如果前面一个数字大于后面的数字（
题目保证输入的数组中没有的相同的数字
），则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对取模的结果输出。即输出Pmod
要求：空间复杂度
O(n)O(n)
，时间复杂度
O(nlogn)O(nlogn)
测试用例
测试用例1
输入：
[1,2,3,4,5,6,7,0]
复制
返回值：
7
复制
测试用例2
输入：
[1,2,3]
复制
返回值：
代码编写思路：使用归并排序
因为我们在归并排序过程中会将数组划分成最小为1个元素的子数组，然后依次比较子数组的每个元素的大小，依次取出较小的一个合并成大的子数组。
这里我们也可以用相同的方法划分，划分之后相邻一个元素的子数组就可以根据大小统计逆序对，而不断往上合并的时候，因为已经排好序了，我们逆序对可以往上累计。我们主要有以下三个阶段。
具体做法：
step1：划分阶段：将待划分区间从中点划分成两部分，两部分进入递归继续划分，直到子数组长度为1.
step2：排序阶段：使用归并排序递归地处理子序列，同时统计逆序对，因为在归并排序中，我们会依次比较相邻两组子数组各个元素的大小，并累计遇到的逆序情况。而对排好序的两组，右边大于左边时，它大于了左边的所有子序列，基于这个性质我们可以不用每次加1来统计，减少运算次数。
step3：合并阶段：将排好序的子序列合并，同时累加逆序对。
图示：
示例代码
classSolution{
public:
intmod=;
intmergeSort(intleft,intright,vectorintdata,vectorinttemp)
{
//停止划分
if(left=right)
return0;
//取中间
intmid=(left+right)/2;
//左右划分合并
intres=mergeSort(left,mid,data,temp)+mergeSort(mid+1,right,data,temp);
//防止溢出
res%=mod;
inti=left,j=mid+1;
for(intk=left;k=right;k++)
temp[k]=data[k];
for(intk=left;k=right;k++)
{
if(i==mid+1)
data[k]=temp[j++];
elseif(j==right+1
temp[i]=temp[j])
data[k]=temp[i++];
购买专栏解锁剩余24%