c++离散化处理大范围和重复数据

关于离散化

有些新手可能会问：离散化是什么？离散化就是将无限空间中有限的个体映射到有限的空间里去。

上面的定义肯定会有人看不懂（其实我刚开始学的时候也看不懂）

用我自己的话来说，就是在不改变数据的相对大小的条件下，对数据进行相应的压缩

可能还是有人看不懂，没关系，我们来看一个例子，顺便来讲一下离散化的基本操作：

现有一个数组：1，100，2367，562，364737，19，1974832947，100，562，2367

如果按照正常的方法，该开1974832947的空间，但是经过离散化后，就不需要

那么step 1：排序

用上面的例子来说，就是将上面的数据排序并去重，得到下面这组数据：

1，19，100，100，562，562，2367，2367，364737，1974832947

然后step 2：通过unique去重使大小与下标对应，并得到去重后的长度，得到下面这组数据：

1，19，100，562，2367，364737，1974832947

接着step 3：通过lower_bound算出离散化后的排列，得到下面这组数据：

1，2，3，4，5，6，7

那么这里就很尴尬了，这组数据无法应用于初始数据

所以在开始，我们多定义1个数组，来记录初始情况下的数据，再用step 3与其进行对应。

最终得到答案：1，3，5，4，6，2，7，3，4，5

下面给出模板：

 View Code
原文地址https://www.cnblogs.com/jasonownblog/p/12906712.html