数据离散化 | 雪落月夜

数据离散化

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

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

使用场景

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

离散化原理

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

离散化特点

离散化不改变原有数据之间的大小关系。
离散化后的数据范围与原数据范围无关，仅与问题数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; //使用原属于找到离散化后缩小的数据（大的找小的）
}

取消回复

(OwO)

ChenShou

2020-03-16 13:47

催更
贴吧表情好评
~~MarkDown???~~

回复
1. xueluopoi
  
  2020-05-24 00:02
  
  好像评论不支持markdown，要不我魔改下这个模板算了...
  
  回复
xueluopoi

2020-02-08 14:26

回复