离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。——摘自百度百科
离散化总体来说还是很有用的，下面先上一段核心代码
struct node { int data,pos; }p[100001]; bool cmp(node x,node y) { return x.data < y.data; } scanf("%d",&n); for(int i = 1;i <= n;i++) { scanf("%d",&p[i].data);//输入数据值 p[i].pos = i;//记录数据的位置 } sort(p + 1,p + n + 1,cmp);//将数据按值从小到大排序 for(int i = 1;i <= n;i++) { if(i == 1 || p[i].data != p[i - 1].data) now++;//如果当前值与上一个值不同，则新建立一个映射 g[p[i].pos] = now;//g数组用来记录一个数据的映射值 h[now] = p[i].data;//h数组用来记录被映射的元素的值 } for(int i = 1;i <= n;i++) f[g[i]]++; //f数组记录一个元素的出现次数
具体有什么作用呢？比如说，你要输入的数据一共有10^5个，但是输入数据的值有可能达到10^9甚至更大。如果我们要统计每一种数据出现了多少次，此时我们显然不可能开数组f[i]来记录数字i出现了多少次，因为会爆空间。此时我们发现，这些数据大部分不是连续的，而且中间有好多空间被浪费了。比如输入1,2,4,8,1000000.这样像10,11,100,1000……等等空间全部被浪费，所以我们要用离散化将这些值映射到一个新数组中，这样我们只需要开与输入数据数量等大的数组了。
这样，原来的元素1,2,4,8,1000000就会被映射成为1,2,3,4,5.同时，离散化还会保持数据的相对大小不变。
例题：
题目描述
LYK拥有n个数，这n个数分别是a1,a2,…,an。
有一天它做了一个梦，在梦里它的这n个数有部分被小偷偷走了，只剩下了m个数b1,b2,…,bm。它想知道有哪些数字被小偷偷走了！
LYK告诉你a和b的值，你需要从小到大的告诉LYK，哪些数字不见了！
输入格式(number.in)
第一行一个数n，第二行n个数ai，表示一开始的数字。
第三行一个数m，第四行m个数bi，表示剩下的数字。
输出格式(number.out)
一行n-m个数，从小到大输出所有被偷走的数字。
这道题当然可以直接排序后O（n）扫一波，不过因为刚刚学完离散化，数据规模也到了10^9，所以使用离散化解题。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct node { int data,pos; }p[100001]; int b[100001],f[100001],g[100001],h[100001]; int now,n,m,k; bool cmp(node x,node y) { return x.data < y.data; } int main() { freopen("number.in","r",stdin); freopen("number.out","w",stdout); scanf("%d",&n); for(int i = 1;i <= n;i++) { scanf("%d",&p[i].data); p[i].pos = i; } sort(p + 1,p + n + 1,cmp); for(int i = 1;i <= n;i++) { if(i == 1 || p[i].data != p[i - 1].data) now++; g[p[i].pos] = now; h[now] = p[i].data; } for(int i = 1;i <= n;i++) f[g[i]]++; scanf("%d",&m); for(int i = 1;i <= m;i++) { scanf("%d",&b[i]); } sort(b + 1,b + m + 1); for(int i = 1;i <= m;i++) { while(h[k] != b[i]) k++; f[k]--; } for(int i = 1;i <= now;i++) { for(int j = 1;j <= f[i];j++) printf("%d ",h[i]); } return 0; }
基本思想与上面相同。