题目：剑指 Offer 51. 数组中的逆序对 - 力扣（Leetcode）
题目的接口：
class Solution { public: int reversePairs(vector& nums) { } };
解题思路：
这一道题，我的思路是用双指针暴力求解，
但这个数组长度，O(N^2)的时间复杂度肯定是不可能把所有样例跑完，
看了大佬的思路，用的是归并排序，（如果不会归并排序，最好先去学一下）
我一开始看了很久没有搞明白为什么，
实际上，这个思路是利用的归并排序的一个特性，具体思路如下：
例： 数组 [ 7, 5, 2, 6, 0, 1, 5, 4 ]
我们就拿这个数组归并到最后一步的时候作为样例：
[ 2, 5, 6, 7 ] 和 [ 0, 1, 4, 5 ]
由于他们通过先前的归并已经是两个有序的数组，
而最后一步就两个数组每个元素比大小，然后尾插到临时数组上，最后再拷贝回来，
重点来了：
第一个数比大小 2 > 0 所以尾插 0 并让第二个数组的下标begin2++，
因为这两个是升序数组，2 > 0，也表明 2 之后的所有数都大于 0 ,
那么这里就有 4 ( mid + 1，也就是第一个数组的长度) 个逆序数对，
那么，当 2 和 4 比较，2 < 4 ，就尾插 2 进临时数组，让第一个数组下标begin1++，
这个时候，继续往下比较，5 > 4， 尾插 4 并让第二个数组的下标begin2++，
因为这两个是升序数组，5 > 4，也表明 5 之后的所有数都大于 4，
但是因为第一个数组已经是第二个数了，所以：
这里就有 3 （ mid + 1 - begin1 （也就是减去第一个数组的下标））个逆序数对。
综上所述，
我们只需要在第一个数组的值 > 第二个数组的值的时候，记录逆序数对 (mid + 1 - begin1) 即可。
下面是代码：
代码
class Solution { public: //计数 int res = 0; int reversePairs(vector& nums) { //创建临时数组 vector tmp(nums.size()); //归并排序，我用的是我学的归并排序模板 merge_sort(nums, tmp, 0, nums.size() - 1); return res; } private: void merge_sort(vector& nums, vector& tmp, int begin, int end) { if(begin >= end) return; //返回 //分治 int mid = (begin + end) >> 1; merge_sort(nums, tmp, begin, mid); merge_sort(nums, tmp, mid + 1, end); //[begin][mid], [mid + 1][end] //两个数组的下标 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; //临时数组的下标 int i = begin; //比较大小之后尾插进临时数组 while(begin1 <= end1 && begin2 <= end2) { if(nums[begin1] <= nums[begin2]) { tmp[i++] = nums[begin1++]; } else { tmp[i++] = nums[begin2++]; //计算这一段的逆序数对数量//具体推导看文章的文字 res += mid + 1 - begin1; //整个思路的核心 } } //将没有插完的值全部尾插进临时数组 while(begin1 <= end1) tmp[i++] = nums[begin1++]; while(begin2 <= end2) tmp[i++] = nums[begin2++]; //将临时数组拷贝回原数组 for(int i = begin; i <= end; i++) { nums[i] = tmp[i]; } } };
过啦！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看
