雪落月夜
停下脚步，看看脚印，怅惘最初
数据离散化
February 8, 2020 · 算法 · 3821次阅读最近做的题（并查集之类的）都用到了数据离散化的技巧，之前没怎么重视过所以现在就稍微记录一下。
使用场景
- 数据（序列）长度很大，但是问题数较少的情况（也就是虽然数据组数量范围给的很大，但问题可能远远小于这个数量范围，那就只考虑问问题需要用到的那一部分数据就可以）
- 并查集中会使用数据本身大小作为节点本身（如编号），此时过大的数据显然不方便计算或者建树，因此先将数据范围缩小。
离散化原理
- 假设题目给出M个提问，通过设置自增变量t及离散值数组a[i]可将每一组提问中输入的数据使用1到M（或M的倍数）之间的数字来代替。换句话说，离散化后题目中的数据可等价代换为只与M有关的较小值，达到减小内存开支的目的。
离散化特点
- 离散化不改变原有数据之间的大小关系。
- 离散化后的数据范围与原数据范围无关，仅与问题数M有关。
简要代码
//a[i]为原数据集，b[i]为离散化后数据集，n为数据个数
void discrete() {
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
if (i == 1 || a[i] != a[i - 1])
b[++m] = a[i]; //m是去重后的个数，仅与问题数量有关
}
}
int query(int x) {
return lower_bound(b + 1, b + m + 1, x) - b; //使用原属于找到离散化后缩小的数据（大的找小的）
}
催更
贴吧表情好评
~~MarkDown???~~
好像评论不支持markdown，要不我魔改下这个模板算了...