离散化：把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时间和空间效率。
即：先把大数据排序，然后对应排序前的顺序，并把排序后数据的下标记录到排序前数据相对应的位置
（百度解释：离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小）
离散化能实现：1.保证离散化后的数据非负且尽可能的小
2.离散化后各数据项之间的大小关系不变，原本相等的也要保持相等。
离散化的实质就是：找数据项在原序列中从小到大排第几。
思路：排序->删除重复元素->索引数据离散化后对应得值
STL 中 unique函数的功能是元素去重。就是将重复的元素保留一个在前面，其余的移动到最后。由于”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序。
#include<iostream> #include<algorithm> #include<cassert> using namespace std; static bool myfunc(int i, int j) { return (i + 1) == j; //return i == j; } int main() { vector<int> a = {1,3,3,4,5,6,6,7};//省略排序步骤 vector<int>::iterator it_1 = a.begin(); vector<int>::iterator it_2 = a.end(); cout<<"去重前的 a : "; for(int i = 0 ; i < a.size(); i++) cout<<a[i]; cout<<endl; //unique(it_1,it_2,cmp);cmp 可以省略
//cmp 表示的是自定义元素是否相等。也就是说通过自定义两个元素相等的规则，来对容器中元素进行去重 unique(it_1,it_2); cout<<"去重后的 a : "; for(int i = 0 ; i < a.size(); i++) cout<<a[i]; cout<<endl; }
vector<int>::iterator nowend; nowend= unique(it_1,it_2); a.erase(nowend,it_2); for(int i = 0 ; i < a.size(); i++) cout<<a[i]; //1 3 4 5 6 7
PS：建议复制下来跑一遍 //13345667 //13456767
模板
//一般模板 int n, a[maxn], t[maxn]; for(int i = 1;i <= n;i++) { scanf("%d", &a[i]); t[i] = a[i];//t是一个临时数组，用来得到离散化的映射关系 } //STL中的sort(排序)，unique(去重)，lower_bound(查找)函数 sort(t + 1, t + n + 1);//排序 int m = unique(t + 1, t + 1 + n) - t - 1;//去重，并获得去重后的长度m for(int i = 1;i <= n;i++) { a[i] = lower_bound(t + 1, t + 1 + m, a[i]) - t; //通过二分查找加速查找 }
PS：附加结构体模板
#include<algorithm> struct Node { int data , id; bool operator < (const Node &a) const { return data < a.data; } }; Node num[MAXN]; int rank[MAXN] , 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;
原文：https://www.cnblogs.com/Shallow-dream/p/11443813.html