首页 > 其他分享 >离散化

离散化

时间:2024-01-23 18:34:38浏览次数:27  
标签:map 下标 int 离散 maps 数组

关于离散化的那些事

离散化,本质上就是一种 hash,我们需要用到的只是数据的排名而不是数据本身,通过映射的方法把跨度大又疏松的数据转化为跨度小的数据。

离散化一般有两种形式,一种是 sort+unique,另一种是 map

sort+unique

首先就是直接用数组排序后去重,将需要用的所有数塞到一个数组里,进行排序,然后去重。所有数据都是有序的,下标就是离散化后的值。查询使用 lower_bound 就可以了。

排序加去重

for(int i=1;i<=n;i++) c[i]=a[i];//复制原数组
sort(c+1,c+n+1);
int tot=unique(c+1,c+n+1)-c; // tot为不重复元素的数量

unique 返回的是一个迭代器,它表示去重后容器中不重复序列的最后一个元素的下一个元素。所以可以这样作差求得不重复元素的数量。

查找

int x=lower_bound(c+1,c+tot+1,y)-c;

查找数据 \(y\) 离散化后的值。通过 lower_bound 找到 \(c\) 数组中第一个大于等于 \(y\) 的数。

制表

int C[N];
for (int i=1;i<=n;i++) C[i]=lower_bound(c+1,c+tot+1,a[i])-c;

将原序列的值全部映射后存在 \(C\) 中。例如 a[7]={12,32,56,-1,35,32},映射后 C[7]={2,3,5,1,4,3}

map

map 就十分好用了,排序去重查找制表一体化。STL 是真的好。先介绍一下 map

map 本质上是一棵红黑树,可以看作下标可以是任意类型的数组,可以实现以下的功能:

  1. map<A,B> maps:建立一个名字为 \(maps\),下标类型为 \(A\),数据类型为 \(B\) 的映射表。
  2. maps[A]=B:把这个“数组”中下标为 \(A\) 的位置的值变为 \(B\),下标可为任意类型。
  3. maps[A]:访问这个“数组”中下标为 \(A\) 的元素。
  4. maps.end():返回最后一个元素的下一个元素的地址。
  5. maps.empty():判断是否为空。
  6. maps.size():返回个数。
  7. maps.erase(A):删除下标为 \(A\) 的元素。
  8. maps.find(x):查找 \(x\) 在映射表中的地址,不存在则返回 maps.end()

那么实现离散化就很简单了:

map <int,int> maps;
int tot=0;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) if(a[i]!=a[i-1]||i==1) maps[a[i]]=++tot;//排序去重制表
int x=maps[y];//查找

这样的话,字符串的离散化也可以轻易实现。

tip

基础的东西不能忘记。

标签:map,下标,int,离散,maps,数组
From: https://www.cnblogs.com/zhouruoheng/p/17982991

相关文章

  • 离散数学 第1章 数理逻辑
    1.1命题1.1.1基本概念断言:一个陈述语句。祈使句、疑问句一定不是断言。命题:要么为真,要么为假,不能二者都是的断言。原子命题(本源命题):一个命题已不能分解成更简单的命题命题和本源命题常用大写字母P、Q、R表示eg.P:4是质数1.1.2命题联结词复合命题:命题和原子命题可通过......
  • 离散化
    不少问题需要将数据范围很大的一些数"缩小"到1~n的范围例如a=[100,-5000,20,9,3]可以离散化到[5,1,4,3,2]其实也就是把这个数组按照从小到大排后之后的排名又有一种就是数组中含有多项重复的值a=[19,19,18,20,20,100,5]可以离......
  • 开关量、数字量、模拟量、离散量和脉冲量它们之间有什么区别?
    开关量、数字量、模拟量、离散量和脉冲量是电子测量和控制系统中经常遇到的不同类型的数据。它们在定义、特性和应用方面存在差异。在电子测量和控制系统设计中,根据实际需求选择合适的数据类型是至关重要的。定义与特点 开关量(SwitchingQuantity)开关量是一种只有两种状态......
  • 基于TIC6000 DSP教学实验箱_数字图像处理操作教程:5-20 图像离散余弦变换(LCD显示)
    一、实验目的学习图像离散余弦变换的原理,掌握图像的读取方法,并实现在LCD上显示余弦变换前后的图像。二、实验原理图像离散余弦变换图像的离散余弦变换广泛用于图像的压缩。对原始图像进行离散余弦变换,变换后DCT系数能量主要集中在左上角,其余大部分系数接近于零,DCT具有适用于图像压......
  • 【领先实践之离散制造行业】MOM全场景,助力光伏单晶行业降本增效
    在光伏单晶行业中,企业面临着提高效率、降低成本和增强市场竞争力的挑战,为了应对这些挑战,用友MOM(制造运营管理)全场景领先实践,基于在光伏单晶行业的成功应用,为光伏单晶行业提供了全方位的生产管理支持。该方案具有以下5大优势:优化供应链通过数据共享和分析,提供实时可视化的供应链信息......
  • 二维离散傅立叶变换的性质
    二维离散傅立叶变换的性质周期性线性微分性质旋转性质令则可分离性空域平移性质频域平移性质平均和对称性质......
  • 基于扁平化BOM的全业务应用领先实践,提升离散制造行业运营效率
    基于扁平化BOM的全业务应用领先实践提升离散制造行业运营效率在离散制造行业中,满足不同客户的需求需要有个性化的方案设计。然而,这也带来了边设计、边采购及边生产的情况,使得计划管理难度增大,信息共享和业务流协同变得困难。为了解决这些挑战,用友推出基于扁平化BOM的全业务应用领先......
  • 离散数学
    计算题1:假设\(p\)表示“我喜欢数学”,\(q\)表示“我会编程”,\(r\)表示“我喜欢阅读”,\(s\)表示“我会游泳”。现有如下命题:(1)如果我不喜欢数学,那么我一定不会编程;(2)如果我会编程,那么我要么喜欢阅读,要么会游泳;(3)我不会游泳且不喜欢阅读。回答:将以上命题翻译成命题......
  • 首个离散元仿真软件EDEM好学吗?有什么学习技巧?
    EDEM是一款首个离散元仿真软件,它被广泛应用于工程领域,特别是在颗粒材料的模拟和分析方面。对于初学者来说,EDEM可能会有一定的学习曲线,但是只要掌握了一些学习技巧,就能够很快上手并熟练运用这款软件。首先,对于初学者来说,最重要的是要了解EDEM软件的基本原理和功能。可以通过阅读E......
  • 【题解】洛谷P1496 火烧赤壁 (离散化)
    P1496火烧赤壁-洛谷|计算机科学教育新生态(luogu.com.cn)我们首先先看数据,n<=20000,数据不多,但是范围大(-10^9<=Ai,Bi<=10^9),这时,就可以用离散化了。但是在这里我们会遇到区间重合的问题(也可以使用区间合并),如下图本题的题意是让我们求出燃烧位置的长度之和。区间重合时只......