题目

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

示例 1:
输入: [7,5,6,4]
输出: 5

1.错误示范


int reversePairs(int* nums, int numsSize) {int i = 0;int j = 0;int sum = 0;for (i = 0; i < numsSize; i++){for (j = i + 1; j < numsSize; j++){if (nums[i] > nums[j]){sum++;}}}return sum;
}

在这里插入图片描述

我们用正常的思路去写，发现就会超出时间限制，因为这样做时间复杂度为O(N^2)，很显然不符合条件

2. 分析

从归并排序(递归)中，可知，我们可以通过临时数组tmp 先排序左数组
再排序右数组，最后将左右数组进行排序

在这里插入图片描述

而这三种情况，正好对应逆序对中的全部从左数组选择、全部从右数组中选择。一个选左数组一个选右数组

逆序对的判断

在这里插入图片描述

全部从左数组选择、全部从右数组中选择，我们只需加上返回值即可

统计出某个数后面有多少个数比它小

在归并合并的过程中，可以得到两个有序的数组，通过有序性快速统计出你逆序对的数量

举例(完整过程解析)

假定left与right数组有序
left=[5,7,9] right=[4,5,8] tmp=[]

第一次循环

在这里插入图片描述

left[begin1] (5)>right[begin2] (4) ,将 right[begin2]放入tmp数组中，并将begin2++
由于是升序排列，所以left数组第一个必是最小的数，而这个最小的数比right所取的数大，则right所取的数(4)比left数组中所有数都小，即为tmp进入排序的第一个数
由于4<5，我们要统计在right数组中有多少数比5小，所以 begin2++

第二次循环

在这里插入图片描述

left[begin1] (5) <= right[begin2] (5) 将left[begin1] 放入 tmp数组中，并将 begin1++
最小的数已经放入tmp数组中，此时left[begin1] (5) 就是次小的数即tmp数组中的第二个数
此时在right数组中 [0,begin2)区间的数都比left[begin1] (5) 小
即 ret += begin2-0
left[begin1] (5) 已经找到>=它的数，begin1++ 遍历下一个left数组中的数

第三次循环

在这里插入图片描述

left[begin1] 1(7) > right [beign2] (5) 将right[begin2] 放入tmp数组中，并将begin2++
在剩余的数中，由于7>5 ，所以 5就为目前最小的数，将其放入 tmp数组中
同时7也没有找到>= 它的数，所以需要 beign2++

第四次循环

在这里插入图片描述

left[begin1] (7) < right[begin2] (8) 将left[begin1] 放入tmp数组中，并将begin1++
在剩余的数中，由于 7<8 ，所以 7就为目前最小的数，放入tmp数组中
此时 right数组[0,beign2）区间小于7
ret+=begin2-0
left[begin1] (7) 已经找到>=它的数,将 begin1++ ,遍历下一个 left数组中的数

第五次循环

在这里插入图片描述

left[begin1] (9) > right[begin2] (8) 将right[begin2]放入tmp数组中，并将begin2++
在剩余的数中，由于 8<9 ，所以 8就为目前最小的数，放入tmp数组中
同时begin2++ ，继续寻找right数组中是否存在>=9的数

循环结束的两种存在情况

由于right数组已经遍历完，所以循环停止，再次判断两个数组是否存在数

在这里插入图片描述

若 left数组没有走完，则left剩余的每一个数都 > 原right数组存在的数
right数组区间[0,begin2) 正好为 right数组的所有数
所以还需累加 ret+= begin2-0

若 right数组没有走完，题中要求为逆序对，即左边大于右边的数，
不成立，所以不用统计无意义

3. 正确代码


int mergesort1(int* nums, int left, int right, int* tmp)//归并排序
{if (left >= right){return  0;}int mid = (left + right) / 2;int leftret = mergesort1(nums, left, mid, tmp);//计算左边区间 [left, mid] 中逆序对的数量 = leftRet，并排序；int rightret = mergesort1(nums, mid + 1, right, tmp);//. 计算右边区间 [mid + 1, right] 中逆序对的数量 = rightRet，并排序int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int i = left;int voeret = 0;//合并左右两个有序区间，并且计算逆序对的数量while (begin1 <= end1 && begin2 <= end2){if (nums[begin1] <= nums[begin2]){//当 nums[begin1] <= nums[begin2] 时，说明此时右边数组已经遍历过的元素都是比// nums[begin1] 小的，因此累加到 voeret 中去voeret += begin2 - (mid + 1);//因为计算的begin2刚开始的边界就为 mid+1tmp[i++] = nums[begin1++];}else{//当 nums[begin1] > nums[begin2] 时，无需统计，直接归并tmp[i++] = nums[begin2++];}}//处理归并排序中剩余的元素；//当左边有剩余的时候，还需要统计逆序对的数量；//当右边还有剩余的时候，无需统计，直接归并。while (begin1 <= end1){voeret += begin2 - (mid + 1);tmp[i++] = nums[begin1++];}while (begin2 <= end2){tmp[i++] = nums[begin2++];}memcpy(nums + left, tmp + left, sizeof(int) * (right - left + 1));return leftret + rightret + voeret;//返回 左区间逆序对数量 + 右区间逆序对数量 + 当前合并过程中产生的逆序对数量
}
int  mergesort(int* nums, int numsSize)
{int* tmp = (int*)malloc(sizeof(int) * numsSize);//因为我们不想一直malloc创建数组所以在外面开辟int ret = mergesort1(nums, 0, numsSize - 1, tmp);free(tmp);tmp = NULL;return ret;
}
int reversePairs(int* nums, int numsSize) {return mergesort(nums, numsSize);
}