离散化介绍
离散化,就是将一组离散的数据,映射成集中的数据。【所以个人觉得应该叫集中化【?……
其思想跟哈希(Hash)类似。
当有些数据因为本身很大或者类型不支持,自身无法作为数组的下标来方便地处理,
而影响最终结果的只有元素之间的相对大小关系时,
我们可以将原来的数据按照从大到小编号来处理问题,即离散化。
引自:OI-Wiki「离散化」
常用来离散化类型的是:大整数、浮点数、字符串。
情况举例
本身很大情况
最常见的题比如:
判断在$N$个数中,某数$a_i$是否存在。
很简单的思路就是:
用个布尔数组bool exist[]
来记录某数是否存在。
但如果数据范围是$1 \le N \le 10^5, 0 \le a_i \le 10^9$,
也就是:数的个数$N$远小于数的范围$a_i$时,
很明显,如果直接用$a_i$作下标来记录,会导致数组开不下。
而对于这道题,$a_i$的值是多少,并没有太大意义,我们只用关心它出现没有。
因此我们可以把这些分散的$a_i$按大小顺序重新编号。
举例
5个数,其分别为:
9463 1 233333333 78 5
此时如果直接以下标来存储,数组就要开为bool exist[233333333 + 5];
。
将其重新编号(映射)为:
4 1 5 3 2
此时数组就可以开为bool exist[5 + 5];
。
类型不支持情况
将题改为:
$N$个字符串,判断某字符串$s_i$是否存在。
这个时候甚至直接不能作为bool exist[]
数组下标了。
可以将其映射为能作为下标的数字。
要查找某字符串,用该映射函数将所寻字符串映射为数字ID
,
然后直接看exist[ID]
是否为$true$即可。
实现方法
思路
上面介绍说到:离散化后的数据只与相互间大小关系有关。
所以对于原数据要先放在另一个容器中排序,得到他们之间的大小关系。
然后该容器中需要去除重复元素,来最大程度节省空间。
比如原数据为$100$个$8$和$1$个$9$。
如果不去重,离散化后$8$会映射为$1$,而$9$会映射为$101$,
去重过后,$8$会映射为$1$,$9$则会映射为$2$了。
这样过后便得到了原数据与新数据的一一映射关系表。
这个时候再将原数据按表全部替换,完成离散化。
所以离散化一共有三个重要操作:
- 对原数据放到另一个容器,并按大小关系排序。
- 去除排好序后容器的重复元素,得到一一映射关系。
- 按照一一映射关系,将原数据替换为新数据。
举例
原数据为:
98 783 1 23333 1 57 912 5 1 98
排序后为:
1 1 1 5 57 98 98 783 912 23333
去重后为:
1 5 57 98 783 912 23333
则得到一一映射关系表:
原数据 | 新数据 |
---|---|
1 | 1 |
5 | 2 |
57 | 3 |
98 | 4 |
783 | 5 |
912 | 6 |
23333 | 7 |
替换后,即离散化为:
4 5 1 7 1 3 6 2 1 4
具体实现
一、大整数离散化
去重操作使用到的是unique
函数,
映射关系表对应,则用lower_bound
这个查找函数。
有关这两个函数的详细信息,可以百度查阅相关资料。
代码:
int raw[MAX_N + 5], //原数据
n, //原数据个数
cont[MAX_N + 5], //临时容器
disc[MAX_N + 5]; //离散化后数据
void discrete()
{
memcpy(cont, raw, (n + 1) * sizeof(int)); //1. 原数据放入另一容器
sort(cont + 1, cont + n + 1); //1. 排序
int disc_len = unique(cont + 1, cont + n + 1) - cont - 1; //2. 去重,并得到去重后的有效长度(运用的是数组地址相减代表长度)。
for (int i = 1; i <= n; i++) //3. 按照一一映射关系,得到离散化序列
disc[i] = lower_bound(cont + 1, cont + disc_len + 1, raw[i]) - cont; //利用lower_bound找到原数据在cont数组中的地址,减去cont头地址后得到离散结果(即cont中下标)
}
运行结果:
二、字符串离散化
【由于暂时没做到相关的题就没做总结2333……
这里就跟字符串哈希的操作是一样的了,
可以查看OI-Wiki上的「字符串哈希」。
其他事项
不去重情况
有时候根据题目要求,相同元素可能会有作用。 如下面的问题:
对于数组$a[i]$,问两区间$(l_1,r_1),(l_2,r_2)$间有多少个相同元素。
如要使用较快的:“bitset
+取并集”的操作,
这里离散化的时候就不要去重,
并采用以下技巧:
用个$cnt[i]$数组,记录$a_i$在bitset
数组$bit[]$出现的次数,
当出现$a_n$时,则使$bit[a_n+cnt[a_n]]++$。
这样,出现了几个$a_n$,就会在$bit[]$中存几个,
取交集的时候就能直接得到个数了。
不去重的原因,是使得相邻两元素离散后的值有差距,
其差距就是该数出现的次数【见上方「本身很大情况」中举的例子】而去重后,两值间则不会有差距,
无法通过这种方法来存储所有出现的$a_n$。