题目：

今天的题，看上去其实不难，用暴力算法是完全可以做的。只不过当数组长度过大之后，就会超时。那么我们就要思考优化的办法了。

暴力算法是对每一个【i】和【j】都去进行比对，那么我们有没有办法只比较一部分去找出这个翻转对呢。

于是很容易想到，如果数组有序的话，比对就会简单很多。但是排序会打乱下表和元素的对应关系，所以我们希望这个比对是在排序的过程中一步步完成的，也就是分治。先排序一部分，比对一部分，然后再排序下一部分，比对下一部分。

于是，就可以想到归并排序，用升序。并且，要在排序之前寻找比对。（因为要保证元素的相对前后位置不变）

这题使用归并排序我个人觉得有这么两个好处：

1.最重要的一个，在归并之前比对左右分区里面的元素，是可以保证相对位置不发生改变的。即左边的元素在归并之前永远在右边元素的左边。什么意思呢。

比如 1 3 2 3 1这个示例数组，我们把它假设为a
该数组分解到最小时，执行两两合并。即a【0】a【1】和a【3】
a【4】。在该次合并之前统计了翻转对的次数，在排序后，a【3】和a【4】的位置虽然发生了交换，但是整体相对位置依旧在a【0】和a【1】的后面，就不会出现漏计的情况。

2.选择升序排列，是因为省时间。用【i】【j】标记左右两个序列。因为对每一个右边序列的元素nums【j】，如果左右两个序列都升序，左边序列的num【i】如果满足了题目条件，则【i】后面的所有元素都满足。于是，就可以拿下一个nums【j】来比对。可以跳过很多次运算。

C++代码附带测试：

#include<iostream> 
#include<vector>
using namespace std;class Solution {
public:int reversePairs(vector<int>& nums) {int size = nums.size();int left = 0;int right = size-1;int result = 0;vector<int> temp(size);mergesort(nums,temp,left,right,result);return result;}void mergesort( vector<int>& nums ,vector<int>& temp,int left,int right,int &result)//归并排序 {if( left >= right) return ;//基线条件，只剩一个元素就是有序的了int mid = left + (right-left)/2;//分隔点mergesort(nums,temp,left,mid,result);//对左区间排序mergesort(nums,temp,mid+1,right,result);//对右区间排序//统计操作 int i = left;int j = mid+1;while( i <= mid && j <= right )//左右区间都是有序的了，进行统计操作{if( (long long )nums[i] > (long long )2*nums[j] )// *2 会超 int 范围{result += ( mid-i +1);//反转对个数j++;}else{i++;}}//合并操作 i = left;j = mid+1;int t = 0;while( i <= mid && j <= right )//进行归并操作{if( nums[i] > nums[j] )//升序排列 {temp[t++] = nums[j++]; }else{temp[t++] = nums[i++] ;}}while( i <= mid )//将左边剩余元素填充进temp中{temp[t++] = nums[i++];}while( j <= right )//将右序列剩余元素填充进temp中{temp[t++] = nums[j++];}t = 0;while( left <= right )//将temp中的元素全部拷贝到原数组[left,right]中{nums[left++] = temp[t++] ;}}
};int main()
{vector<int> nums = {1,3,2,3,1};Solution s;int ans = s.reversePairs(nums);cout<<ans<<endl;
}

为了防止忘记了归并排序原理，这里还是附上归并排序原理动图