「查漏补缺」离散化
我们要操作的数的范围很大,比如10^8
但真正操作到的数不多
我们关心的只是那些真正操作到的数,以及它们之间的大小关系
把所有操作到的数全部提取出来,按大小重新编号!
这样就建立了一个映射
举个例子:
原数组ax [-1, 120, 13, 45, 12, 12]
排序去重后得到[-1, 12, 13, 45, 120]
映射完后得到新的ax数组 [1,5,3,4,2,2]
一种比较简单的写法:
将所有操作到的数用一个数组存起来,然后排序,去重,该数在数组中的下标就是映射后的新的编号。
参考代码:
int a[10],data[10];
void discrete(int *a,int n){
for(int i=0;i<n;i++)data[i]=a[i];
sort(data,data+n);
int cc=unique(data,data+n)-data;
for(int i=0;i<n;i++)
a[i]=upper_bound(data,data+cc,a[i])-data;
}