离散化

离散化可以分为两种离散化,是否保序

保序

若需要保持原有的顺序

map<int,int> mp;
int idx;
int get(int x)
{
    if(!mp[x]) mp[x]=idx++;
    return mp[x];
}

不保序,需要排一下序

我现在知道的两种写法

一,二分
vector<int> alls;
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
编号依靠,find函数
int find(int x) {
    return lower_bound(alls.begin(),alls.end(),x) - alls.begin() + 1;
}
下标从1,开始了
二,map映射
map<int,int> mp;
for(int i=0;i<n;i++) mp[alls[i]]=0;
int sz=0;
for(auto &p:mp) p.second=++sz;
for(int i=0;i<n;i++) alls[i]=mp[alls[i]];
上一篇:Delphi 实现Ping命令


下一篇:(POJ-2528)Mayor‘s posters(区间覆盖+离散化)