01
2019
08

详解归并排序和树状数组两种求逆序对数得思路

首先通过题目看看如何考察逆序数,什么是逆序数?逆序数就是找前面有几个比自己大的数

即如果i<j&&a[i]>a[j] 则a[i]和a[j]构成一个逆序对

1111.png

这里排序求交换次数比正好就是我们前面讲到的逆序对吗?

因此我们首先就想到了o(logn)方法的归并排序 mergesort(int l,int r)

归并排序的思路就是:先二分分到不能再分,保证(l<r),再将两个有序的序列合并起来。

如一个序列a[7]={100,29,8,9,10,5} 对齐归并排序步骤如下:

100,29,8,9,10,5

{100,29,8}  {9,10,5}

{100} {29,8}  {9,10} {5}

合并:

{100}{8,29},{9,10}{5}

{8,29,100},{5,9,10}

{5,8,9,10,29,100}

我们发现当和并的时候如果左边的a[p]>a[q],则产生了逆序,p-mid这一段的数都对a[q]构成逆序,因为他们是从小到大有序的了。

因此ans+=mid-p+1就是逆序对数

写出代码:

#include<iostream>
using namespace std;

int a[6]={100,29,8,9,10,5},b[6];
int ans=0; 

void merge(int l,int mid,int r){
		cout<<l<<" "<<mid<<" "<<r<<" "<<endl; 
		int p=l,q=mid+1,i=l;
		while(p<=mid&&q<=r){//左右两部分都不要为空 
			//从左半数组复制到辅助数组 
			if(a[p]<=a[q]){
				b[i++]=a[p++];
			}else{     //从右半数组复制到辅助数组
				b[i++]=a[q++];
				ans+=mid-p+1;
			}	
		}
		//处理剩下的,一部分变为空了 
		while(p<=mid){
			b[i++]=a[p++];	
		} 
		while(q<=r){
			b[i++]=a[q++];
		}
		//写会原来的数组 
		for(int j=l;j<=r;j++){
			a[j]=b[j];
		}
}
void mergesort(int l ,int r){
	if(r-l>0){
		int mid=(l+r)/2;
		int p=l,q=mid+1,i=l; //p为左边的第一个,q为右边的第一个	
		mergesort(l,mid);
		mergesort(mid+1,r); 
		merge(l,mid,r);
	}	
}
int main(){
	mergesort(0,5);
	cout<<ans;
	return 0;
}

//100,29,8,9,10,5
//0-2  3-5    {100,29,8}  {9,10,5}
//0-1  3-4    {100,29} 8  {9,10} 5 
//


下面来看看树状数组,树状数组用于求解a[1]-a[i]区间和及单点修改问题。

#include<iostream>
using namespace std;
int n,a[10010],c[10010];

int lowbit(int x)
{
return x&(-x);
}

//C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i]
//单点修改更新了a[i] 要更新对应的c[xxx],其中c[xxx]包含a[i]
int update(int i,int k){
while(i<=n){
c[i]+=k;
i+==lowbit(i);
}
}
//求1到i的区间和a[1]+...+a[i]
//c[x1]+c[x2]+..+c[xx]  xx=i...i-lowbit[i]..1
int getsum(int i){
int sum=0;
while(i>0){
sum+=c[i];
i-=lowbit(i);
}
return sum;
}



int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
update(i,a[i]);//输入等于单点修改值
}

return 0;
}

如何用树状数组求解逆序数呢?

对于序列t 100,29,8,9,10,5

     1            2           3          4            5          6

a[100]=1 a[29]=1  a[8]=1  a[9]=1   a[10]=1  a[5]=1

即update(100,1),update(29,1),update(8,1)......

然后

getsum(100)为a[1]+...+a[100]      t[1]前面小于t[1]的个数  i-getsum(100) 就是第i个数前面大于t[i]的个数

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=1e5+5;
const int mod=99999997;
int n,c[N],temp[N],t[N];
long long ans=0;
struct node
{
  int w;
  int id;
}a[N],b[N];
int R()
{
  int f=0;
  char c;
  for(c=getchar();c<'0'||c>'9';c=getchar());
  for(;c<='9'&&c>='0';c=getchar())
    f=(f<<3)+(f<<1)+c-'0';
  return f;
}
bool comp(node x,node y)
{
  return x.w<y.w;
}
inline void merge(int x,int mid,int y)
{
  int i=x,j=mid+1,head=x;  
  while(i<=mid&&j<=y)
  {
    if(c[i]<=c[j])
      temp[head++]=c[i++];
    else
    {
      ans=(ans+mid-i+1)%mod;
      temp[head++]=c[j++];
    }
  }
  while(i<=mid)  temp[head++]=c[i++];
  while(j<=y)  temp[head++]=c[j++];
  for(i=x;i<=y;i++) 
    c[i]=temp[i];
}
inline void mergesort(int a,int b)
{
  if(a==b)  return;
  int mid=(a+b)/2;
  mergesort(a,mid);
  mergesort(mid+1,b);
  merge(a,mid,b);
}

int lowbit(int x){
	return x&(-x);
}

void update(int i,int k){
	while(i<=n){
		t[i]+=k;
		i+=lowbit(i);
	}
}

int getsum(int i){
	int sum=0;
	while(i>0){
		sum+=t[i];
		i-=lowbit(i);
	}
	return sum;
}


int main()
{
  //freopen("a.in","r",stdin);
  n=R();
  for(int i=1;i<=n;i++)
  {  
    a[i].w=R();
    a[i].id=i;
  }
  for(int i=1;i<=n;i++)
  {    
    b[i].w=R();
    b[i].id=i;
  }
  sort(a+1,a+n+1,comp);
  sort(b+1,b+n+1,comp);
  for(int i=1;i<=n;i++)
    c[b[i].id]=a[i].id;
  for(int i=1;i<=n;i++){
  	update(c[i],1);
  	ans=(ans+i-getsum(c[i]))%mod;
  }
  cout<<ans<<endl;
  return 0;
}





参考资料:树状数组概念         https://www.cnblogs.com/xenny/p/9739600.html

                  归并排序求逆序数  https://blog.csdn.net/qq_41550842/article/details/81215935

                  树状数组求逆序数  https://blog.csdn.net/m0_38033475/article/details/80330157


« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。