题目
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] 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+1 tmp[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); }
4.递归展开图
以下标从0到3 的数组进行演示
