关于求逆序对的三种办法

tonyfang posted @ 2015年8月15日 14:59 in Algorithm with tags c++ Algorithm , 388 阅读

其实以前我对逆序对并不是太了解,也只知道暴力求法,今天看了下怎么求逆序对个数的三种方法。

1. 暴力:时间复杂度$O(n^2)$,空间复杂度$O(n)$。常数为1.

很简单的暴力,$for(i→[1,n])$,$for(j→[1,i))$,暴力枚举统计即可。

2. 树状数组 时间复杂度$O(nlogn)$,空间复杂度$O(n)$,其中时间复杂度常数为2(因为需要快排一遍),空间复杂度的常数为4(离散+树状数组+原数+原数的位置($pos$))。

怎么做呢?首先树状数组元素都是0,每次在离散后的位置上插入一个数1,统计在这个数前面的1有多少个,统计即可。

这篇文章写的比较清楚:传送门

代码:

 

# include <stdio.h>
# include <algorithm>
# include <stdlib.h>
using namespace std;
int c[1000010],n;
struct ps {
	int pos,data;
}a[1000010];
int d[1000010]; //离散后的数 
inline int lowbit(int x) {return x&(-x);}
inline int cmp(struct ps a,struct ps b) {
	return a.data<b.data;
}
inline void modify(int pos,int x) {
	while(pos<=n) {
		c[pos]+=x;
		pos+=lowbit(pos);
	}
}
inline int query(int pos) {
	int sum=0;
	while(pos>0) {
		sum+=c[pos];
		pos-=lowbit(pos);
	}
	return sum;
}
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i].data),a[i].pos=i;
	sort(a+1,a+n+1,cmp);
	int ord=1;
	d[a[1].pos]=ord;
	for (int i=2;i<=n;++i) {
		if(a[i].data==a[i-1].data) d[a[i].pos]=ord;
		else d[a[i].pos]=++ord;
	}
	long long ans=0;
	for (int i=1;i<=n;++i) {
		modify(d[i],1);
		ans += i-query(d[i]); 
	}
	printf("%lld\n",ans);
	return 0;
}

3. 归并排序求逆序对。

时间复杂度$O(nlogn)$,空间复杂都$O(n)$,常数为2.

归并的时候找到有交叉的部分进行统计即可。

 

# include <stdio.h>

using namespace std;

int n, a[1000010];
int tmp[1000010];
long long ans=0;

inline void merge(int l,int mid,int r) {
	int i=l, j=mid+1, k=l;
	while(i<=mid&&j<=r) {
		if(a[i]>a[j]) {
			tmp[k++]=a[j++];
			ans+=mid-i+1;	
		} else tmp[k++]=a[i++];
	}
	while(i<=mid) tmp[k++]=a[i++];
	while(j<=r) tmp[k++]=a[j++];
	for (int i=l;i<=r;++i) a[i]=tmp[i];
}

void mergesort(unsigned int l,unsigned int r) {
	if(l<r) {
		int mid=(l+r)>>1;
		mergesort(l,mid);
		mergesort(mid+1,r);
		merge(l,mid,r);
	}
}
int main() {
	scanf("%d",&n);
	for (int i=0;i<n;++i) scanf("%d",&a[i]);
	mergesort(0,n-1);
	printf("%lld\n",ans);
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter