【优化策略】离散化

概念

离散化是算法设计中处理大数据范围时的关键技巧，它将大范围的数据映射到有较小的的离散空间中，同时保持数据的相对关系。

本质：将原始数据映射到紧凑的连续整数空间

数学表示：建立映射函数 f: ℝ → ℤ，满足 x < y ⇒ f(x) < f(y)

典型场景：

坐标范围极大但数据点稀疏（1e9范围仅1e5个点）

需要构建线段树/树状数组但值域过大

数据值本身无意义而只需保留相对大小关系

实现

//方式一：排序 + 去重 + 二分查找（在disc中依次查找a的每个元素，返回在disc中的下标） 
#include <iostream>
#include <algorithm>
using namespace std; 
const int N = 1e5 + 10;
int a[N],n;
int disc[N],pos;//二分找x，返回下标 
int binary_search(int x)
{int left = 1,right = pos;	while(left < right){int mid = (left + right) / 2;if(disc[mid] >= x) right = mid;else left = mid + 1;`}return left
}int main() 
{cin >> n;for(int i=1;i<=n;i++) {cin >> a[i];disc[++pos] = a[i]; //pos在这里起到枚举下标的作用 }sort(disc+1,disc+pos+1); //默认排升序pos = unique(disc+1,disc+pos+1) - (disc+1); //给元素去重 pos在这里接收去重后元素的个数 for(int i=1;i<=n;i++){	printf("%d离散化后的值为%d\n",a[i],binary_search(a[i]));} return 0;
}

//方式二：排序 + 哈希表去重并且记录离散化后的值 
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std; 
const int N = 1e5 + 10;
int a[N],n;
int disc[N],pos;
unordered_map<int,int> mp;int main() 
{cin >> n;for(int i=1;i<=n;i++) {cin >> a[i];disc[++pos] = a[i]; }sort(disc+1,disc+pos+1); //默认排升序int cnt = 0;for(int i=1;i<=pos;i++){int x = disc[i];if(mp.count(x)) continue;mp[x] = ++cnt; //哈希表中储存的是 disc中的各个元素 及其 从小到大分别是第几号 }for(int i=1;i<=n;i++){	printf("%d离散化后的值为%d\n",a[i],mp[a[i]]);} return 0;
}