离散化可以分为两种离散化,是否保序
保序
若需要保持原有的顺序
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]];