如果暴力时间复杂度是o(N2)
用归并,我们可以把数组一分为二,左边和右边的逆序对数量相加在加上横跨左右两边逆序对数量
(*截图来源于acwing基础算法课)
因为i是第一个大于j 的位置且上数组已经排序好,所以i后面的数都大于j
此方法相对于暴力来说每次只要找到第一个比j的数就可以确定后面数对
#include <iostream> using namespace std; int n; const int N=100005; int a[N],tem[N]; long long mergeSort(int a[],int l,int r){//用递归的板子解决逆序对数量 ;操作的数组,左,右 if(l>=r) return 0;//当区域只有一个或空时没有逆序对 long long res=0; int mid=l+r>>1, i=l, j=mid+1, k=0; res=mergeSort(a,l,mid)+mergeSort(a,mid+1,r);//先把左右区域的逆序对数量加上 //以下基本为归并的板子 while(i<=mid&&j<=r){//当i j一个达到终点时跳出 if(a[i]<=a[j]) tem[k++]=a[i++]; else{ res+=mid-i+1; tem[k++]=a[j++];//逆序对增加的操作,上的第一个i比j大,那么i之后的都比j大 } } //把另一组还未加的归并掉 while(i<=mid) tem[k++]=a[i++]; while(j<=r) tem[k++]=a[j++]; //物归原主,tem转进a for(int i=l,j=0;i<=r;i++,j++) a[i]=tem[j]; return res; } int main(int argc, char** argv) { cin>>n; for(int i=0;i<n;i++){ scanf("%d",&a[i]); } cout<<mergeSort(a,0,n-1)<<endl; return 0; }
统计数组内满足两两大小关系的问题可以用归并的思想