关于求逆序对的三种办法

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

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

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;
}

 

NCERT Evs Question P 说:
2022年9月24日 01:39

Environmental education or Environmental studies makes people understand the importance of renewable energy. Non-renewable sources of energy like petrol, diesel etc are the major sources of the world’s pollution. NCERT Evs Question Paper Class 9 In Environment education using renewable sources, like solar energy, wind energy etc, is encouraged as it is imperative in the fight against global warming. Environmental education or Environmental studies makes people understand the importance of renewable energy. Non-renewable sources of energy like petrol, diesel etc are the major sources of the world’s pollution.

booksyllabus.com 说:
2023年4月20日 21:44

Booksyllabus 2023 is open in PDF download. directorate of Government Assessment, Open Test on June 2023. Snap-on the association of the specific subject referred to in the table underneath. booksyllabus.com A Pdf record will be opened on the screen. Snap-on ‘Free Download’ Option and Download the We gave standard syllabus 2023 to all subjects both in english and tamil Medium.


登录 *


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