将大数据映射到一个较小的值域来处理

STL实现离散化

（1）排序（sort函数）
（2）去重（unique函数）：返回去重之后的尾迭代器（或指针），即去重之后末尾元素的下一个位置
（3）二分索引（lower_bound或upper_bound函数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int n,res,tot,a[MAXN],b[MAXN];
int main() 
{
	scanf("%d",&n);
	for(register int i=1;i<=n;i++) 
    {
		scanf("%d",&a[i]);
		b[++tot]=a[i]; //b[]是a[]的副本 
	}
	sort(b+1,b+1+tot);  //第一步：排序 
	res=unique(b+1,b+1+tot)-(b+1);  //unique函数计算出去重后的元素个数，存在res中
	for(register int i=1;i<=n;i++) 
    {
		a[i]=lower_bound(b+1,b+1+res,a[i])-b;  //lower_bound函数进行索引 
	}
	return 0;
}

Hash表实现离散化

（也叫散列表）

szu-acm
oi_wiki
浅谈离散化