离散化

杂项 / discrete

本地源文件：docs/misc__discrete.md

离散化

简介

离散化是一种数据处理的技巧，本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的 全/偏序 关系．

通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照排名来处理问题，即离散化．

用来离散化的可以是大整数、浮点数、字符串等等．

实现

将一个数组离散化，并进行查询是比较常用的应用场景．

方法一

通常原数组中会有重复的元素，一般把相同的元素离散化为相同的数据．

方法如下：

  1. 创建原数组的副本．
  1. 将副本中的值从小到大排序．
  1. 将排序好的副本去重．
  1. 查找原数组的每一个元素在副本中的位置，位置即为排名，将其作为离散化后的值．
---|---

参考实现中使用的 STL 算法可参考 [STL 算法](../../lang/csl/algorithm/)．

同样地，我们也可以对 [std::vector](../../lang/csl/sequence-container/#vector) 进行离散化：

---|---

方法二

根据题目要求，有时候会把相同的元素根据输入顺序离散化为不同的数据．

此时再用 std::lower_bound() 函数实现就有些困难了，需要换一种思路：

  1. 创建原数组的副本，同时记录每个元素出现的位置．
  1. 将副本按值从小到大排序，当值相同时，按出现顺序从小到大排序．
  1. 将离散化后的数字放回原数组．
---|---

### 复杂度

对于方法一，去重复杂度为 𝑂(𝑛)O(n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)，排序复杂度为 𝑂(𝑛log⁡𝑛)O(nlog⁡n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)，最后的 𝑛n![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 次查找复杂度为 𝑂(𝑛log⁡𝑛)O(nlog⁡n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．

对于方法二，排序复杂度为 𝑂(𝑛log⁡𝑛)O(nlog⁡n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．

故两种方法的总时间复杂度都为 𝑂(𝑛log⁡𝑛)O(nlog⁡n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．

空间复杂度为 𝑂(𝑛)O(n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．

## 习题

  * [[HAOI2014] 贴海报](https://www.luogu.com.cn/problem/P3740)
  * [[NOI2015] 程序自动分析](https://www.luogu.com.cn/problem/P1955)

* * *

>  __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/misc/discrete.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/misc/discrete.md "edit.link.title")
>  __本页面贡献者：[Ir1d](https://github.com/Ir1d), [GavinZhengOI](https://github.com/GavinZhengOI), [Tiphereth-A](https://github.com/Tiphereth-A), [ksyx](https://github.com/ksyx), [PlanariaIce](https://github.com/PlanariaIce), [Early0v0](https://github.com/Early0v0), [Enter-tainer](https://github.com/Enter-tainer), [Marcythm](https://github.com/Marcythm), [ouuan](https://github.com/ouuan), [senlinjun](https://github.com/senlinjun), [TrisolarisHD](mailto:orzcyand1317@gmail.com)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用