离散化算法实例讲解

说到离散化，可能很多人不知道这是什么，小编简单给大家介绍一下，后面会详细说明，离散化是程序设计中一个常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中，只考虑需要用的值。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。要掌握这个思想，必须从大量的题目中理解此方法的特点。例如，在建造线段树空间不够的情况下，可以考虑离散化。

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

一、什么是离散化？

离散化（Discretization），把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：

原数据：1, 999, 100000, 15；处理后：1,3,4,2。

原数据：{100, 200}，{20, 50000}，{1, 400}；处理后：{3,4}，{2,6}，{1,5}。

有的时候，我们会发现对于一个序列，它的值域很大，对应算法的复杂度是 Θ(值域) 的。离散化是程序设计中一个常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中，只考虑需要用的值。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。例如，在建造线段树空间不够的情况下，可以考虑离散化。

离散化的原理和实现都很简单。为了确保不出错且尽可能地提高效率，我们希望离散化能实现以下几种功能：

1. 保证离散化后的数据非负且尽可能的小

2. 离散化后各数据项之间的大小关系不变，原本相等的也要保持相等。

由此，找出数据项在原序列中从小到大排第几就是离散化的关键。可以通过下面的方法以 O(n logn) 的时间复杂度完成离散化，n 为序列长度。

二、离散化两种方法

离散化一共有两种方法，方法一重复元素离散化后的数字相同，方法二重复元素离散化后的数字不相同。用的最多的是方法一。

（一）方法一：重复元素离散化后的数字相同

例如：对于序列 [105，35，35，79，-7]，排序并去重后变为 [-7，35，79，105]，由此就得到了对应关系 -7->1, 35->2, 79->3, 105->4。

基本的步骤可以分为：

1. 用一个辅助的数组把你要离散的所有数据存下来。

2. 排序，排序是为了后面的二分。

3. 去重，因为我们要保证相同的元素离散化后数字相同。

4. 索引，再用二分把离散化后的数字放回原数组。

对应的代码如下：

#include<algorithm> // 头文件 
 
const int MAXN = 1e6+4;
//n 原数组大小 num 原数组中的元素 lsh 离散化的数组 cnt 离散化后的数组大小 
int lsh[MAXN], cnt, num[MAXN], n;
 
for (int i=1; i<=n; i++) {
    scanf("%d",&num[i]);
    lsh[i] = num[i];	
}
 
sort(lsh+1 , lsh+n+1);//排序
cnt = unique(lsh+1, lsh+n+1) - lsh - 1;//去重
 
//二分查找
for(int i=1; i<=n; i++) {
    num[i] = lower_bound(lsh+1 , lsh+cnt+1 , num[i]) - lsh;
}

在这段代码中，num[] 经过离散，范围就变成了 m。

数据解析

比如，这组数据：

1,23424,242,65466,242,0

排序后得到：

0,1,242,242,23424,65466

然后会去重，得到：

0,1,242,23424,65466

然后离散化的到：

1,3,2,4,2,0

注意事项：

（1）去重并不是把数组中的元素删去，而是重复的部分元素在数组末尾，去重之后数组的大小要减一。

（2）二分的时候，注意二分的区间范围，一定是离散化后的区间。

（3）如果需要多个数组同时离散化，那就把这些数组中的数都用数组存下来。

（二）方法二：重复元素离散化后的数字不相同

例如：对于序列 [105，35，35，79，-7]，排序后变为 [-7，35，35，79，105]，由此就得到了对应关系 -7->1，35->2，35->3，79->4，105->5。

基本的步骤可以分为：

1. 用一个辅助的数组把你要离散的所有数据存下来。

2. 排序。

3. 枚举着放回原数组。

对应的代码如下：

#include<algorithm>
 
struct Node {
    int data , id;
    bool operator < (const Node &a) const {
	return data < a.data;
    }
};
 
const int MAXN = 1e5+4;
Node num[MAXN];//原数组
int rank[MAXN];//离散化后数组
int n;
 
for (int i=1; i<=n; i++) {
    scanf("%d",&num[i].data);
    num[i].id = i;
}
 
sort(num+1 , num+n+1);
 
for (int i=1; i<=n; i++) {
    rank[num[i].id] = i;
}

这种方法复杂度比上面那一种要优，但不能处理重复元素。它直接用结构体存储原本的数列的元素的位置，然后排序以后将他们再重新赋值。那么 rank[] 就是结构体 num[] 离散化后的结果。

数据解析

原始数据：

data: 3 6 5 10 8
id : 1 2 3 4 5

排序以后：

data: 3 5 6 8 10
id: 1 3 2 5 4

离散化以后：

data: 3 5 6 8 10
id: 1 3 2 5 4
rank: 1 2 3 4 5

再按原来的顺序排列：

data: 3 6 5 10 8
rank: 1 3 2 5 4