面试题36：数组中的逆序对

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

分析

如果采用简单粗暴的方法，即遍历数组，对每个数，检查后面的每一个数是否小于它。时间复杂度为O(n²)。

实际上我们可以采用归并排序来解决这个问题，只需要在归并每一个数字时，通过计算而不是遍历的方式得到后面有多少个元素小于它(常数时间)。这样总的时间复杂度就是归并排序的时间复杂度为O(nlgn)，不并且需要额外的O(n)的空间。这又是一个“以空间换时间”的做法。

而具体的计算方法如下：归并时从后往前归并，如果前面的数大于后面的，说明他们是有序的，不构成逆序对；否则说明前面的数大于后面的数字，并且可以推断出前面的数大于后面中该数字之前的所有数字。例子如下：

• 首先，7<8，此时临时数组中后半部分的数字为8，count加0。
• 然后7和6,7>6，构成逆序对，并且6之前的所有元素均和7构成逆序对，count加3。临时数组中值为7,8。
• 5<6，不构成逆序对，count加0.临时数组中后半部分值为6,7,8。
• 5>3，所以5和2,3都构成逆序对，count加2.临时数组中值为5,6,7,8。
• 4>3，所以4和2,3都构成逆序对，count加2，临时数组中值为4,5,6,7,8。
• 接下来两步，1<2和3，不构成逆序对，直接放入临时数组即可，值为1,2,3,4,5,6,7,8。

所以以上1,4,5,7,2,3,6,8数组中共有7组逆序对。

代码如下：

```void Merge(vector& v,int left,int mid,int right,vector& tmp,int& count) { int i=mid,j=right,k=right; while(i>=left && j>mid) { if(v[i]=left) tmp[k--]=v[i--]; while(j>mid) tmp[k--]=v[j--]; for(i=left;i<=right;++i) { v[i]=tmp[i]; } }

void MergeSort(vector& v,int left,int right,vector& tmp,int& count) { if(right-left>1) { int mid=left+(right-left)/2; MergeSort(v,left,mid,tmp,count); MergeSort(v,mid+1,right,tmp,count); Merge(v,left,mid,right,tmp,count); } else { Merge(v,left,left,right,tmp,count); } }

int InversePairs(vector v) { int count=0; vector tmp; tmp.resize(v.size()); MergeSort(v,0,v.size()-1,tmp,count); return count; } ```

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往