设计师个人作品集网站,遵义网站建设制作,浙江省住房建设厅网站首页,gta5买房子网站建设一、离散化#xff08;discretization#xff09;在算法和数据结构中指的是将连续的输入数据映射到离散的值或者范围#xff0c;从而使得处理和计算变得更高效。通常用于处理大范围或者无限可能的输入#xff0c;以便将其转化为有限的、可以有效处理的范围。
离散化的定义…一、离散化discretization在算法和数据结构中指的是将连续的输入数据映射到离散的值或者范围从而使得处理和计算变得更高效。通常用于处理大范围或者无限可能的输入以便将其转化为有限的、可以有效处理的范围。
离散化的定义
离散化的主要目的是将连续的值或大范围的值映射到一个有限的集合中以便进行高效的存储和处理。这通常通过对连续的数据进行排序、分组、或者映射来实现。
离散化的步骤
排序和编号对所有唯一的连续值进行排序然后为这些值分配一个唯一的编号。映射使用一个映射函数将原始数据的每个值转换为新的编号或索引。
应用场景 区间压缩在处理大范围的整数值时通过离散化可以将这些值映射到一个较小的范围。例如处理1到10000的值时可以将它们映射到1到100的范围内。 数据结构优化在某些数据结构中如树状数组或线段树需要将离散化后的值作为索引来优化查询和更新操作。
离散化在以下方面有应用
机器学习将连续特征转换为离散类别简化模型处理例如将年龄分段成“青年”、“中年”、“老年”。图像处理将图像数据的连续像素值转换为离散的色彩级别提高处理效率。数据压缩将连续信号如音频或视频离散化以减少存储需求。数据库设计将连续数据映射到离散值用于更高效的数据索引和查询。
这些应用帮助简化计算、提高效率或改善模型性能。
例子
例子 1区间压缩
假设有一组连续的坐标值[100, 150, 300, 600, 900]。我们希望将这些值映射到更小的范围。 排序和编号 排序后的值[100, 150, 300, 600, 900]对这些值进行编号100 - 1, 150 - 2, 300 - 3, 600 - 4, 900 - 5 映射 原始值 100 映射到编号 1原始值 150 映射到编号 2原始值 300 映射到编号 3原始值 600 映射到编号 4原始值 900 映射到编号 5这样我们就将原始的连续值压缩到了 [1, 2, 3, 4, 5]这使得后续的数据结构如线段树或树状数组的操作更为高效。
例子 2二维离散化
假设有一组二维坐标值[(10, 20), (15, 30), (30, 60)]。我们需要将这些坐标值离散化。 提取和排序 X轴坐标[10, 15, 30]Y轴坐标[20, 30, 60]对X轴坐标编号10 - 1, 15 - 2, 30 - 3对Y轴坐标编号20 - 1, 30 - 2, 60 - 3 映射 (10, 20) 映射到 (1, 1)(15, 30) 映射到 (2, 2)(30, 60) 映射到 (3, 3)这样我们将原始的连续坐标转换成离散的坐标对数据结构的处理如二维树状数组将更加高效。
总结
离散化的关键是将原始的、可能是连续或无限范围的数据转化为有限且可处理的编号或索引。这样不仅优化了存储空间也提高了数据处理的效率。 二、在算法中“映射”是指将一个集合中的每个元素通过某种规则或函数转换为另一个集合中的元素的过程。这一概念广泛应用于数据处理、函数设计和数据结构中。以下是映射的详细解释
1. 基本定义
映射可以被视为一个函数 ( f: A \rightarrow B )其中 ( A ) 是定义域( B ) 是值域。对于定义域中的每个元素 ( a \in A )映射函数 ( f ) 将其转换为值域中的元素 ( b \in B )。形式上这可以表示为 ( f(a) b )。
2. 示例 数学中的映射一个简单的数学映射是 ( f(x) x^2 )它将每个实数 ( x ) 映射到它的平方 ( x^2 )。 数据结构中的映射在哈希表中映射是通过哈希函数将键key映射到对应的值value。例如键 name 可能映射到值 Alice。
3. 应用 数据转换在数据处理过程中可以将数据从一种格式转换为另一种格式。比如映射函数可以将用户输入的字符串转换为对应的内部数据结构。 离散化在离散化过程中映射用于将连续的数据转换为离散的值。例如将地理坐标映射到一个有限的网格系统中。
4. 复杂映射
映射不仅限于一对一关系还可以是多对一多个输入映射到一个输出或一对多一个输入映射到多个输出。例如在关系数据库中某一用户ID可能映射到多个订单记录。
5. 映射的属性
单射Injective每个定义域的元素映射到值域中唯一的元素不存在不同的输入映射到相同的输出。满射Surjective定义域中的每个元素都映射到值域中的某个元素使得值域中的每个元素至少被映射一次。双射Bijective既是单射又是满射即每个定义域的元素都有唯一的值域元素且值域中的每个元素都有唯一的定义域元素。
映射在算法中扮演着重要角色它使得数据转化、存储和处理变得更加系统化和高效。
了解了什么是离散化和映射接下来直接开始做题用题目实践才是最好的。 题目区间和
假定有一个无限长的数轴数轴上每个坐标上的数都是 0。
现在我们首先进行 n次操作每次操作将某一位置 x上的数加 c。
接下来进行 m次询问每个询问包含两个整数 l 和 r你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n和 m。
接下来 n 行每行包含两个整数 x 和 c。
再接下来 m 行每行包含两个整数 l 和 r。
输出格式
共 m 行每行输出一个询问中所求的区间内数字和。
数据范围
≤x≤ 1≤n,m≤,≤l≤r≤, −10000≤c≤10000
输入样例
3 3
1 2
3 6
7 5
1 3
4 6
7 8输出样例
8
0
5 离散化的特点 值域大个数少。 可以把这n个数映射到它的下标。 常见的问题 1. 数组a中有重复元素去重 2. 如何算出映射后的值二分
此题把下标映射后前缀和求解即可。 #includeiostream
#includevector
#includealgorithmusing namespace std;
typedef pairint,int PII;/*定义pairint,int类型为PII就相当于取了一个别名就是方便使用的时候不输入那么复杂又长的东西。*/
const int N3e510;
/*因为有三个坐标所以是用的3e510的范围。
输入的n个xm个l,r就是n2m个坐标因为n和m都是10的五次方所以就是3乘10的5次方多10是故意开的害怕越界嘛。*/
int a[N],s[N];
/*这个就是求的区间和只不过前面还有些步骤所以这个a[N]数组是存储的值不是坐标哈s[N]
还是和前缀和一样是放的前缀和的值。*/
vectorPII add,query;
/*观察题目得到输入的位置x和插入的值c与后面输入的区间两个边界l,r一样都是一次输入一对
的数进去所以这里定义了一个PII类型的vector来存储要操作的东西。这里面add是存储插入的位置x和值c而query是查询区间并求出指定区间的和所以query存储的是边界lr的位置*/
vectorint alls;
/*alls是存储所有的位置的不管是刚开始的x还是l,r都存在里面后面会操作的很有用处。记住vector是c里面的可变数组所以在进行和数组类似的操作时也可以像数组那样使用切记。*/int find(int x){int l0,ralls.size()-1;while(lr){int midlr1;//这里是整数没有小数所以可以用位运算。if(alls[mid]x) rmid;//二分的第一个模板相当于求最小值的那个不用加1。else lmid1;}return r1;//这里你写l1也可以反正最后二分l是约等于r的都可以。/**注意返回的是r1就是最低是返回1因为我要求前缀和所以就这样。/
}
/*这个函数是利用的二分查找来查找x在alls可变数组里面的位置也就是x在alls可变数组的数组下标是多少。这其实就是离散化了alls数组在之前的操作后已经变得井然有序每一个输入的坐标值x,l,r在alls里面都有对应的位置这就已经将原来范围大数目少且离散不好处理的坐标给放在了alls数组里面所以要注意这个alls数组里面存的是坐标如果要求对应的值的话那么就是例如要想查询x位置上的值的话那么就是1、先找到x这个坐标在alls数组里面的哪个位置对应的是alls数组的哪个下标。 2、找到了以后就能迅速的在alls数组里面找到x坐标所在的位置。 3、找到位置后就直接能找到x所对应的值了。 这就是离散化1、vector存输入的位置坐标2、在这个vector里面找到需要的位置坐标。
3、找到以后就可以像之前那样正常操作了想查值就查值想求前缀和就求前缀和。*/int main(){int n,m;cinnm;for(int i0;in;i){int x,c; cinxc;add.push_back({x,c});alls.push_back(x);}
/*输入n,m并且输入xc这x,c是插入所需要的值所以将这两个值存到add这个vector里面。然后顺便把位置x存入alls这个可变数组里面。*/for(int i0;im;i){int l,r;cinlr;query.push_back({l,r});alls.push_back(l);alls.push_back(r);}
/*输入l,r并将后面查询求前缀和所需要的值l,r给存入到query这个vector里面去同时l,r这两个表示位置的数也全部存到alls这个可变数组内。*/ sort(alls.begin(),alls.end());//排序alls里面的所有坐标值alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重并调整里面的坐标值。
/*所有输入的关于位置的数也就是所谓的坐标已经排序去重并调整大小了经过了这两步得到的是
有序的且中间没有空位的新的alls可变数组这对于后面的离散化是很重要的。*/ for(auto item:add){int xfind(item.first);//找x这个坐标在alls数组里面的数组下标是多少。a[x]item.second;//在alls数组里面找到x所在的位置后就直接执行c的插入操作就可以了。}//插入操作for(int i1;ialls.size();i) s[i]s[i-1]a[i];//注意ialls.size()是从下标1开始的不是0.
/*这里还是和求前缀和是一样的在求前缀和之前都要定义一下前缀和的表示在我看来就是定义一种性质嘛注意这里是i从1开始不从0开始是为了避免边界问题。*/for(auto item:query){//这个不一定要写成item随便写自己喜欢的单词就好不影响的。int lfind(item.first),rfind(item.second);//分别求l,r在alls数组里面的位置。printf(%d\n,s[r]-s[l-1]);//这就是求前缀和直接用公式就可以这是一维前缀和哦。}//查询并求前缀和的操作/*这里面的first,second就是键值因为我的add和query的vector都是PII类型的也就是pairint,int类型的就拿这里来说这里query的item.first指的是输入的l而item.second指的是输入的r。*/return 0;
} 上面是y总的分析我觉得分析的挺好的。
以上就是我对于算法里面的离散化的看法与理解就这样吧。
