离散化简明教程

wangjiajian · 2023-09-22 13:54:42 · 算法·理论

使用桶的时候，如果数据过大无法储存，可以将数据离散化，映射到一个小的连续区间。

for(int i=1; i<=n; i++)
    b[i] = a[i];
sort(b+1, b+1+n);
int cnt = unique(b+1, b+1+n) - (b+1);
for(int i=1; i<=n; i++)
    a[i] = lower_bound(b+1, b+1+cnt, a[i]) - b;

这样就通过 b 数组完成了对稀疏的数组 a 的离散化。