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

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