离散化模板

  • A+
所属分类:算法

假设需要存储一些键值对,它们的 key 分别为{1, 8, -10, 499, 231, 76, 21747483647}——一组无序且边界极大的数

直接存数组是不行的 arr[21747483647]、arr[-10] 都不合理

如果直接使用 map 去存,每次插入都是一次树型的调整,虽然大致是 nlogn,但是肯定要大一点的。对于只在初始化阶段建表,后期不再改动的情况,是挺浪费的

这个时候使用离散化是更好的方法

// 把 pairs 按照 key 递增顺序排序,cmp 自己实现
sort(pairs, pairs + n, cmp);

for (int i = 0; i < n; i++){
   
  v[i] = pairs[i].value;
}

for (int i = 0; i < n; i++){
   
  k[i] = pairs[i].key;
}

使用时很方便,比如要找 key=499 对应的数据,只需要

v[lower_bound(k, k + n, 499) - k];

可以 define 一个宏,用起来方便

#define KLOC(X) (lower_bound(k, k + n, (X)) - k)

lower_bound()是纯二分,logn,所以说这个也是 nlogn,比 map 快的 nlogn

vector 版本:

sort(pairs.begin(), pairs.end(), cmp);
...
v[lower_bound(k.begin(), k.end(), 499) - a.begin()];
w3cjava