当前位置：首页 > news >正文

39.离散化与哈希

news 2025/8/17 17:28:34

一、离散化

1.简介

离散化是一种数据处理的技巧，可以通过降低数据规模来降低算法的复杂度和实现难度，其保证数据在哈希以后仍然保持原来的全/偏序关系。

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

原数据	1	999999	50505	23	4396	101
离散化	1	6	5	2	4	3

几乎所有的数据类型都可以使用离散化，只要它本身存在全/偏序关系即可，例如：大整数、浮点数、字符串等等。离散化通常都会和其他算法结合使用，作为一种前置的数据处理方式，因此它的应用面非常广泛。

2.离散化方法

离散化的实现方式很灵活，只要能够维持原本的关系即可，而且离散化的方式也需要根据题目的要求来变化。我们给出一个常用的离散化方法：

对原数据进行排序，然后去除排序后数组中的重复元素。这里可以使用 STL 提供的一个方法 unique 去重，使用它需要头文件 #include <algorithm>。使用 unique 之前必须先排序，否则会产生意料之外的错误。
调用 unique 后会返回去重后的分界线的地址指针，减去数组起始地址后我们就得到了元素去重以后的元素个数了。
最后将原数组与排序去重后的数组进行一一对应即可。我们对原数组中的每个数都用二分查找的方式在排序去重后的新数组中找到其现在的下标，这个下标就是其对应的离散化结果。
离散化的时间复杂度是 $O(nlog⁡n)O(n\log n)$ 。
模板代码如下所示：

for(ll i = 1; i <= n; i++)tmp[i] = arr[i];
sort(tmp + 1, tmp + n + 1);
ll len = unique(tmp + 1, tmp + n + 1) - (tmp + 1);
for(ll i = 1; i <= n; i++)arr[i] = lower_bound(tmp + 1, tmp + len + 1, arr[i]) - tmp;