本文共 2525 字，大约阅读时间需要 8 分钟。
很多算法的复杂度与数据中的最大值有关，比如树状数组和纯用数组实现的一对一标记。
时常会遇到这种情况：
- 数据的范围非常大或者其中含有负数，但数据本身的个数并不是很多（远小于数据范围）。
在这种情况下，如果每个数据元素的具体值并不重要，重要的是他们之间的大小关系的话，我们可以先对这些数据进行离散化，使数据中的最大值尽可能小且保证所有数据都是正数。
1. 什么是离散化
数据离散化是一个非常重要的思想。
为什么要离散化?当以权值为下标的时候，有时候值太大，存不下。 所以把要离散化的每一个数组里面的数映射到另一个值小一点的数组里面去。
例如，有这样一个长为5的序列：102131511，123，9813186，-611，55。其中有非常大的数以及负数，会给许多算法的实现带来困扰，我们可以把这个序列离散化，使它变成这样：5，3，4，1，2。各个元素间的大小关系没有任何改变，但数据的范围一下子就变得很舒服了。
我们来看一下定义：
- 离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。（by百度百科）
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。
例如：
-
原数据：102131511，123，9813186，-611，55；
-
原数据：{100,200}，{20,50000}，{1,400}；
2. 离散化的方法
离散化的原理和实现都很简单。
为了确保不出错且尽可能地提高效率，我们希望离散化能实现以下几种功能：
- 保证离散化后的数据非负且尽可能的小
- 离散化后各数据项之间的大小关系不变，原本相等的也要保持相等。
由此，找出数据项在原序列中从小到大排第几就是离散化的关键。
- 所以：咱们离散化的思想可以转换为以下几步：
- 排序
- 去重（不一定必须去重）
- 建立映射（新的索引）关系
2.1 使用数组标记实现
这种方法直接用结构体存储原本的数列的元素的位置，然后排序以后将他们再重新赋值。那么rank[]就是结构体a[]离散化后的结果。
#include using namespace std;const int MAXN = 1e4+5;int n,Rank[MAXN];struct Node{ int data,index;}node[MAXN];bool compare(Node &a,Node &b){ return a.data > n; for(int i=0;i > node[i].data; node[i].index=i; } sort(node,node+n,compare); for(int i=0;i
举个例子：
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
rk:1 2 3 4 5
在按原来的顺序我们就可以直接得到离散化后的索引：
data: 3 6 5 10 8
rk: 1 3 2 5 4
2.2 通过STL中的函数实现
2.2.1 unique 函数
unique()函数是一个去重函数，STL中unique的函数 unique的功能是去除相邻的重复元素(只保留一个),还有一个容易忽视的特性是它并不真正把重复的元素删除。具体用法如下：
int num[100];int len=unique(num,mun+n)-num;
返回的是num去重后的尾地址，之所以说比不真正把重复的元素删除，其实是，该函数把重复的元素一到后面去了，然后依然保存到了原数组中，然后返回去重后最后一个元素的地址，因为unique去除的是相邻的重复元素，所以一般用之前都会要排一下序。
2.2.2 通过数组实现
#include using namespace std;const int MAXN = 1e4+5;int n,arr[MAXN],t[MAXN];int main(){ cin >> n; for(int i=0;i > arr[i],t[i]=arr[i]; sort(t,t+n); int len=unique(t,t+n)-t; for(int i=0;i
2.2.3 通过vector实现
#include using namespace std;const int MAXN = 1e4+5;int n,arr[MAXN];int main(){ cin >> n; vector v; for(int i=0;i > arr[i],v.push_back(arr[i]); sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());//去重，并且删除去重后，后面的部分 for(int i=0;i
离散化后查询的问题(采用的如上代码的离散方式)：
1、通过离散后的值查询离散前的值：
若离散后的值为x，那么对应的离散前的值为v[x]；
2、通过离散前的下标查询离散后的值：
若离散前的下标为i，那么对应的离散后的值为arr[i]；
3、通过离散前的值查询离散后的值：
如果没有相应的保存的话，首先要确定y在v[]中的位置，或者在arr[]中的位置，前者可以使用pos = lower_bound(v.begin(),v.end(), y) - v.begin()。那么pos即为下标，通过第二步再查询就好了。
转载地址：http://tiyof.baihongyu.com/