https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/题目链接
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
第一种想法是直接遍历整个数组让每一个数字和后面的数进行比较，如果这个数比后面的小的话就加1。这样显然时间复杂度O(n^2)会tle，但是可以把这个程序当作对拍程序，和小和问题的代码相似，这里就不贴了，可以借鉴小和问题。
https://www.cnblogs.com/RainzzZ/p/12745535.html
第二种想法就是利用归并排序，递归的思想。方法非常简单，利用Mergesort函数递归，分解成小数组，进行排序的时候左右两个指针p1,p2分别指向两个数组的首位，如果左指针指向的数比右指针指向的数大的话让结果加上左指针指向的数字*右边数组末尾到指针位置的乘积，并让左指针向后移动一位。否则就让右指针向后移。
class Solution { public: int reversePairs(vector<int>& nums) { if(nums.size()<2) return 0; return Mergesort(nums,0,nums.size()-1); } int Mergesort(vector<int>& nums,int l,int r){ if(l==r) return 0; int mid=l+((r-l)/2); return Mergesort(nums,l,mid)+Mergesort(nums,mid+1,r)+merge(nums,l,mid,r); } int merge(vector<int>& nums,int l,int mid,int r) { int *help=(int *)malloc(sizeof(int)*(r-l+1)); int i=0; int p1=l; int p2=mid+1; //cout<<p1<<" "<<p2<<" "<<r<<endl; int res=0; while(p1<=mid && p2<=r) { res += (nums[p1] > nums[p2] ? (r-p2+1) : 0 ); help[i++]= (nums[p1] > nums[p2] ? nums[p1++] : nums[p2++] ); } while(p1<=mid) { help[i++]= nums[p1++]; } while(p2<=r) { help[i++]= nums[p2++]; } for(int i=l;i<=r;i++) { nums[i]=help[i-l]; } //cout<<res<<endl; return res; } };
原文：https://www.cnblogs.com/RainzzZ/p/12750716.html