什么是离散化及其实现方式

如大家所熟悉的在一些场景或题目中常常会遇到数据跨度较大的一堆数据。如果需要用连续空间存储则会有大量空闲的空间并且遍历的时间复杂取决于最大和最小值的间距。如果不关系数据的具体大小只关心数据的相对顺序那么就可以用到本文重点离散化。那么什么是离散化离散化是指将无限的数据映射到有限的空间中并保留原来的全 / 偏序关系。举个例子实现原理以下以一维数组给出示例将数据离散化到[0, n-1]的范围例观察发现10 - 4,3 - 0,8 - 2,9 - 3,4 - 1这正式排序后的次序。因此排序是必不可少的一个步骤。