Dark`Kris

Private blog

I'm spark , hope you fire


逆序对

今天想写一个专题:如何求一串数中的逆序对个数。

具体来讲,一共有两种比较好的方法:

  1. 归并排序
  2. 树状数组

两种方法的比较

先来比较一下两个方法:

方法 时间复杂度 空间复杂度 代码长度 理解难度
归并排序 相比较长(除非你用STL) 容易
树状数组 短小精悍(用不到STL) 一般

好吧,其实并没有多大区别,但是还是建议这两个方法都学一下


归并排序

其实就是在归并排序的时候发现一个较大的数在前面,计算一个逆序对个数,废话不多说,直接看代码理解吧。

代码

void Msort(int l,int r)
{
	int ret[500002];
	if(l!=r)
	{
		int mid=(l+r)/2;
		Msort(l,mid);Msort(mid+1,r);
		int i=l,j=mid+1,k=l;
		while(i<=mid&&j<=r)
		{
			if(a[i].num<=a[j].num)
			{
				ret[k]=a[i].num;
				i++;k++;
			}else
			{
				ret[k]=a[j].num;
				j++;k++;ans=(ans+mid-i+1)%P;//加上逆序对个数(模P)
			};
		};
		while(i<=mid)
		{
			ret[k]=a[i].num;
			i++;k++;
		};
		while(j<=r)
		{
			ret[k]=a[j].num;
			j++;k++;
		};
		for(int i=l;i<=r;i++)a[i].num=ret[i];
	};
};

树状数组

详细解释请看我的另一篇博文《树状数组》,具体原理与代码就不写了。(偷一下懒)

相关链接

另一篇博文《树状数组》

到这里就结束了。感谢惠读。

Tips

Cancel

Thanks a lot,I will be better!

scan possible
scan possible
Scan and give tips as you wish

OpenAlipayScan it and give tips as you wish

Wait a minute,Loading