「查漏补缺」离散化

· · 个人记录

我们要操作的数的范围很大,比如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;
}