离散化

算法：离散化算法及其实现 - 知乎 (zhihu.com)

离散化的概念¶

首先，什么是离散化？

离散化就是比相对大小。

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

原数：131021 546412 973324

离散化后数据：1 2 3

离散化的用途¶

当有些数据本身很大， 自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理（当然也可以哈希）。当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。

（这样就可以开桶了）

离散化的写法¶

我们只需要维护两个事情不变：

1. 保证离散化之后的数据尽可能地小而且非负。

2. 离散后的数据要保持原本的大小关系，原本相等的也要保持相等，否则就是错误的离散。（一对一的双射）

找出原数据在序列中的序位就是离散化的关键。

STL-vector 实现：¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int a[maxn];
vector<int> b;
for(int i=1;i<=n;i++) {
    scanf("%d",&a[i]);
    b.push_back(a[i]);
}
sort(b.begin(),b.end(),cmp); // 不是结构体，不用写cmp
b.erase(unique(b.begin(),b.end()),b.end()); // 直接删掉，不用维护size
for(int i=1;i<=n;i++)
    a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin();
    //算出在a[i]在b中的下标 并覆盖

解释：

unique去重，返回无重复序列的尾迭代器
lower_bound返回第一个大于等于val的迭代器（upper是大于）

输入a[i]之后紧接着保存同样的b[i]作为副本。然后对副本b进行去重，并保存b数组去重后的长度（size）。

然后开始离散化，直接把对应元素转换成相应的数组下标即可。

源数据和离散数字相互转化¶

对于离散后的数字找原数字，只需要访问离散化的\(b[i]\)存储

原数字找离散数字，则需要利用 lower_bound() 找出在离散化的\(b[i]\)的位置