数据离散化

February 8, 2020 · 算法 · 1879次阅读

最近做的题(并查集之类的)都用到了数据离散化的技巧,之前没怎么重视过所以现在就稍微记录一下。

使用场景

  1. 数据(序列)长度很大,但是问题数较少的情况(也就是虽然数据组数量范围给的很大,但问题可能远远小于这个数量范围,那就只考虑问问题需要用到的那一部分数据就可以)
  2. 并查集中会使用数据本身大小作为节点本身(如编号),此时过大的数据显然不方便计算或者建树,因此先将数据范围缩小。

离散化原理

  1. 假设题目给出M个提问,通过设置自增变量t及离散值数组a[i]可将每一组提问中输入的数据使用1到M(或M的倍数)之间的数字来代替。换句话说,离散化后题目中的数据可等价代换为只与M有关的较小值,达到减小内存开支的目的。

离散化特点

  1. 离散化不改变原有数据之间的大小关系。
  2. 离散化后的数据范围与原数据范围无关,仅与问题数M有关。

简要代码

//a[i]为原数据集,b[i]为离散化后数据集,n为数据个数
void discrete() {
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        if (i == 1 || a[i] != a[i - 1])
            b[++m] = a[i]; //m是去重后的个数,仅与问题数量有关
    }
}

int query(int x) {
    return lower_bound(b + 1, b + m + 1, x) - b; //使用原属于找到离散化后缩小的数据(大的找小的)
}

板子

最后编辑于3年前

添加新评论

  1. 2020-03-16 13:47

    催更

    贴吧表情好评

    ~~MarkDown???~~

    回复
    1. 2020-05-24 00:02

      好像评论不支持markdown,要不我魔改下这个模板算了...

      回复
  2. 2020-02-08 14:26

    回复