离散化

📹 配套视频讲解：离散化（acwing 视频课，原网址 Trilium 导出时未保留，待回填）

在接触前先思考一下数组值与下标的灵活应用

前面双指针那里曾使用值作为下标这样一来能实现判重的操作

比如值 1 2 2 4 5

下标 0 1 2 3 4

记录为

值 0 1 2 0 1 1

下标 0 1 2 3 4 5

这样就很容易知道2这个数出现了几次

这是一种将空间放大的操作（使得第二个数组很多下标对应的值没有意义）

反过来

还可以用下标去做值这就是要接触的离散化

比如

值 1 0 0 0 2 0 0 2 0 0 4 0 0 0 0 0 5

下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

我们发现原数组中有太多数据没有意义

完全可以不去管那些0 想个办法把有意义的数据取出来存储

然后还得有办法将它还原回去这才有意义

所以可以把有意义的数的下标取出来只存储这个下标就够了

本例中只有0 4 8 11 17这几个下标有东西

所以就存这些下标就够了

模板是要排序去重那是对于有些情况下还要记录一些其他位置的下标这样就会出现重复的情况就使得映射关系不够精简在这里是不需要考虑去重的问题的但是呢为了统一就记一下吧 sort() erase(unique(begin,end),end)

这样得到的数组为

值 0 4 8 11 17

下标 0 1 2 3 4

但是没什么意义它得记录有意义的数据呀光下标有什么用

所以得二分查找再构建一个数组它的下标与这个数组的下标相对应但是值是存的该数组中存的下标所对应的原本数组的值（有意义的值）

要是这样

值 1 2 2 4 5

下标 0 1 2 3 4

这样一来就将那长度17的数组离散化成了这么一个长度为5的数组了

核心——记录有意义的下标对下标排序去重 find找对应位置使数据有意义