关于离散化的那些事
离散化,本质上就是一种 hash,我们需要用到的只是数据的排名而不是数据本身,通过映射的方法把跨度大又疏松的数据转化为跨度小的数据。
离散化一般有两种形式,一种是 sort+unique
,另一种是 map
。
sort+unique
首先就是直接用数组排序后去重,将需要用的所有数塞到一个数组里,进行排序,然后去重。所有数据都是有序的,下标就是离散化后的值。查询使用 lower_bound
就可以了。
排序加去重
for(int i=1;i<=n;i++) c[i]=a[i];//复制原数组
sort(c+1,c+n+1);
int tot=unique(c+1,c+n+1)-c; // tot为不重复元素的数量
unique
返回的是一个迭代器,它表示去重后容器中不重复序列的最后一个元素的下一个元素。所以可以这样作差求得不重复元素的数量。
查找
int x=lower_bound(c+1,c+tot+1,y)-c;
查找数据 \(y\) 离散化后的值。通过 lower_bound
找到 \(c\) 数组中第一个大于等于 \(y\) 的数。
制表
int C[N];
for (int i=1;i<=n;i++) C[i]=lower_bound(c+1,c+tot+1,a[i])-c;
将原序列的值全部映射后存在 \(C\) 中。例如 a[7]={12,32,56,-1,35,32}
,映射后 C[7]={2,3,5,1,4,3}
。
map
map
就十分好用了,排序去重查找制表一体化。STL 是真的好。先介绍一下 map
。
map
本质上是一棵红黑树,可以看作下标可以是任意类型的数组,可以实现以下的功能:
map<A,B> maps
:建立一个名字为 \(maps\),下标类型为 \(A\),数据类型为 \(B\) 的映射表。maps[A]=B
:把这个“数组”中下标为 \(A\) 的位置的值变为 \(B\),下标可为任意类型。maps[A]
:访问这个“数组”中下标为 \(A\) 的元素。maps.end()
:返回最后一个元素的下一个元素的地址。maps.empty()
:判断是否为空。maps.size()
:返回个数。maps.erase(A)
:删除下标为 \(A\) 的元素。maps.find(x)
:查找 \(x\) 在映射表中的地址,不存在则返回maps.end()
。
那么实现离散化就很简单了:
map <int,int> maps;
int tot=0;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) if(a[i]!=a[i-1]||i==1) maps[a[i]]=++tot;//排序去重制表
int x=maps[y];//查找
这样的话,字符串的离散化也可以轻易实现。
tip
基础的东西不能忘记。
标签:map,下标,int,离散,maps,数组 From: https://www.cnblogs.com/zhouruoheng/p/17982991