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

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


分析

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

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

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

1,4,5,7
2,3,6,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上:点我前往

[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")