这个题目如果没有限制你的时间复杂度，那么它的在O（n
2） 里面完成的话， 那么就很简单 了。
但是如果发求你在O（n）的时间复杂度里面完成。那么这还是有点挑战性的。
题目的分析：对于逆序对的理解
先看方法：
如上面的所示，对于该算法以，我们首先将数组划分成一个一个的数字（为了排序），然后拆分成了
两个己排好序的数组。
那么如何计数逆序对呢？
如上图在（a）图中：
是两个排好序的数组，一个是5，7，另一个是4，6.
我们用两个指针P1和P2，一个指向左边那么数组的未尾，一个指向右边那么数组的未尾。
于是我们比较P1和P2所指向的这两个数，由于P1指向的数大于P2指向的数，又由于我们右
边的那个数组是从小到大排好序的，于是逆序数就是P2加它左边的数=2了。然后我们将
P1指向的数放入辅助数组中，用P3指示。P1左移一位。P2保持不动
（b）图中：
由于P1比P2小，因此此时P2指向的数无用了。因为P1应该是在左边的数组中属于最大的了
于是将P2指向的数复制到P3。然后将P2左移一位。
（C）图中：
和（a) 图相似了。
看代码：
#ifndef INVERT_DATA_COUNT_H#define INVERT_DATA_COUNT_H#include<iostream>int invertPairCore(int *arr,int *copy,int start,int end); int invertDataPairCount(int *arr,int Length); int invertDataPairCount(int *arr,int Length){ if(arr==NULL||Length==0){ return 0; } int *copy=new int[Length]; /*
for(int i=0;i<Length; i++){
copy[i]=arr[i];
}
*/ int InverpairCountSum=invertPairCore(arr,copy,0,Length-1); delete[] copy; return InverpairCountSum; }int invertPairCore(int *arr,int *copy,int start,int end){ if(start==end){ copy[start]=arr[start]; return 0; } int mid=(end-start)/2; //相当于归并排序，先排好序，分成两组 int leftInvertPair=invertPairCore(arr,copy,start,start+mid); int rightInvertPair=invertPairCore(arr,copy,start+mid+1,end); int i=start+mid; int j=end; int indexCopy=end; int pairCount=0; //核心步骤，和图解差不多的意思。 while(i>=start&&j>=start+mid+1){ if(arr[i]>arr[j]){ copy[indexCopy--]=arr[i--]; pairCount+=j-(start+mid+1)+1; }else{ copy[indexCopy--]=arr[j--]; } }
//对剩下的数的处理，也就是在两数组比较的时候还有剩下数据拷贝到copy数组中。 for(;i>=start; --i){ copy[indexCopy--]=arr[i]; } for(; j>=start+mid+1; --j){ copy[indexCopy--]=arr[j]; } //返回值。
return pairCount+leftInvertPair+rightInvertPair; }#endif
测试代码
#include"invertDataCount.h"int main(){ int arr[4]={7,5,6,4}; std::cout<<invertDataPairCount(arr,4); }
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655472.html
