1.什么是离散化
数据离散化是一个非常重要的思想。
为什么要离散化?当以权值为下标的时候,有时候值太大,存不下。 所以把要离散化的每一个数组里面的数映射到另一个值小一点的数组里面去。...我们来看一下定义:离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。(by百度百科)
通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。...例如:
原数据:1,999,100000,15;处理后:1,3,4,2;
原数据:{100,200},{20,50000},{1,400};
处理后:{3,4},{2,6},{1,5};
但是离散化仅适用于只关注元素之间的大小关系而不关注元素本身的值...假如你想写的更加专业就要采用以下步骤:
1、排序
2、去重
3、索引
首先我们要对所要进行离散化的数据进行排序:一般使用sort对数组或结构体排序。...cnt 离散化后的数组大小
int lsh[MAXN] , cnt , num[MAXN] , n;
for(int i=1; i<=n; i++) {
scanf("%d",&num[i]);