离散化

定义

把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率,即在不改变数据相对大小的条件下,对数据进行相应的缩小。类
似一个按数据大小给数据标号的过程。

使用

由定义可知,当数据很大(无论是本身大小还是数据跨度)且只需要这些数据的相对属性进行运算时,可以使用离散化预处理数据以减少时间(某些时候使用动态数组还可以减少空间)复杂度

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=500+5;
const int maxm=100001;
int n,m;
int a[maxn],b[maxn];
int main(){
	scanf("%d",&amp;n);
	for(int i=1;i<=n;i++){
		scanf("%d",&amp;a[i]);
		b[i]=a[i];
	}
        //以下是离散化的核心代码
	sort(a+1,a+n+1);//离散化前(因为需要用unique)所以应该先给待离散化的数组排序
	int size=unique(a+1,a+n+1)-a-1;//size为离散化后元素个数
	for(int i=1;i<=n;i++){
		b[i]=lower_bound(a+1,a+n+1,b[i])-a;
	}
	sort(b+1,b+n+1);//排序离散化后的数组
	return 0;
}

对于第3步(就是循环内部分),lower_bound返回第1个不小于a[i]的值的指针,而upper_bound返回第1个大于a[i]的值的指针,因此给lower_bound的返回值加1可以得到与使用upper_bound相同的结果。

发表评论

电子邮件地址不会被公开。 必填项已用*标注