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

如大家所熟悉的，在一些场景或题目中，常常会遇到数据跨度较大的一堆数据。如果需要用连续空间存储，则会有大量空闲的空间，并且遍历的时间复杂取决于最大和最小值的间距。

如果不关系数据的具体大小，只关心数据的相对顺序，那么就可以用到本文重点离散化。

那么，什么是离散化？

离散化是指，将无限的数据，映射到有限的空间中并保留原来的全 / 偏序关系。

举个例子：

实现原理

以下以一维数组给出示例，将数据离散化到[0, n-1]的范围

例：

观察发现10 -> 4,3 -> 0,8 -> 2,9 -> 3,4 -> 1这正式排序后的次序。因此排序是必不可少的一个步骤。