离散化及模板详解

这篇具有很好参考价值的文章主要介绍了离散化及模板详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

⭐写在前面的话:本系列文章旨在复习算法刷题中常用的基础算法与数据结构,配以详细的图例解释,总结相应的代码模板,同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的C++基础的学习者。若C++基础不牢固,可参考:10min快速回顾C++语法,进行语法复习。

离散化

基本思想

首先,离散化是指数值域非常大,例如 1 − 1 0 6 1-10^6 1106,但是个数相对较少,例如只有 1 0 3 10^3 103个, 但在我们的程序中需要通过这些数值作为下标,且依赖的是这些数值之间的顺序关系(当然通常这些数是有序的)。如果为了这 1 0 3 10^3 103个数而开一个 1 0 6 10^6 106的数组过于浪费空间,因此我们可以采用离散化的方法,将这些数映射到 0 − 1 0 3 0-10^3 0103上,这个过程就叫做离散化。

注意:这里的映射数字指的是元素的下标数字,而非元素本身的数值。

算法思路

对于有序数组进行映射,其基本思路如下:

离散化及模板详解

针对可能存在的两个问题,有以下的解决方法:

1.数组中可能存在重复元素 ==> 对数组进行去重

常见写法:用cpp中的库函数来实现。

unique函数:将数组中的元素去重,并且返回去重后数组的尾端点。

离散化及模板详解

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

2.如何算出x离散化后的值 ==> 用二分法

int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    // 映射到1, 2, ...n
    // 不加1的话是从0开始映射。
    return r + 1;
}

模板

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    // 映射到1, 2, ...n
    // 不加1的话是从0开始映射。
    return r + 1;
}

例题:区间和

假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。

现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加c。

接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r]之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行,每行包含两个整数 x 和 c。

再接下来 m 行,每行包含两个整数 l 和 r。

输出格式

共 m 行,每行输出一个询问中所求的区间内数字和。

数据范围

− 1 0 9 ≤ x ≤ 1 0 9 −10^9≤x≤10^9 109x109,
1 ≤ n , m ≤ 1 0 5 1≤n,m≤10^5 1n,m105,
− 1 0 9 ≤ l ≤ r ≤ 1 0 9 −10^9≤l≤r≤10^9 109lr109,
− 10000 ≤ c ≤ 10000 −10000≤c≤10000 10000c10000

输入样例

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例

8
0
5
题目分析

数据范围很大,因此不能用哈希表,并且数轴上的数字是离散的,整体是稀疏的,我们可以采用离散化的方式进行映射。

  • add : 保存真实的下标和相应的值
  • alls : 用来保存真实的下标和映射的下标的关系
  • query : 用来保存查询的左右两个端点
  • a : 保存映射的坐标所对应的值
  • s: 保存映射的坐标所对应的值的前缀和

第一步: 输入数轴上所对应的值

for(int i=0;i<n;i++)
{
	int index,x; cin>>index>>x;
	add.push_back({index,x});//index 是我们真实的下标 x是数值
	alls.push_back(index);// 将真实的下标和我们想象的坐标建立映射关系
}

第二步: 输入我们的查询的区间

for(int i=0;i<m;i++)
	{
		int l,r; cin>>l>>r;
		query.push_back({l,r});//保存查询的区间
		
		alls.push_back(l);
		//将其左右端点也映射进来,目的是可以让我们在虚拟的映射表里找到,这对于我们后面的前缀和操作时是十分的方便的。
		//如果当我们在虚拟的映射表里找的时候,如果没有找到左右端点,那么前缀和无法求。
		alls.push_back(r);
	}

第三步: 将虚拟的坐标排序并去重

为啥去重:
是因为当我们输入
3 5
3 6
即给数轴上3的点加5 再加 6时。此时我们的坐标映射表里有了两个3 3 但其实它们对应的是同一个坐标。故需要去重,排序。

 sort(alls.begin(), alls.end());//排序
 alls.erase(unique(alls), alls.end());//去重(坐标)

第四步:根据真的坐标,来找到对应虚拟的坐标,将其位置加上其相对应的数值。
根据真的坐标找其对应的映射的坐标,用二分来查找。

int find(int x)
{
	int l=0,r=alls.size()-1;
	while(l<r)
	{
		int mid=l+r>>1;
		if(alls[mid]>=x) r=mid;
		else l=mid+1;
	}
	return l+1;//  因为要求前缀和,故下标从1开始方便,不用额外的再处理边界。
}

for(int i=0;i<add.size();i++)
{
		int x=find(add[i].first);
		a[x]+=add[i].second;
} 

最后一步: 求前缀和,根据我们的查询的区间来输出区间的和

for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
	
for(int i=0;i<query.size();i++)
{
	int l=find(query[i].first),r=find(query[i].second);
	cout<<s[r]-s[l-1]<<endl;
}
code
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

typedef pair<int, int>PII;

const int N = 300010;

int n,m;
int a[N],s[N];// a[N]是储存的数组,s[N]储存前缀和

vector<int> alls;
// 定义了两个pair的变量,add和query。
vector<PII> add, query;

int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x)r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

int main()
{
    cin >> n >> m;
    // 对数字与坐标输入
    for(int i = 0; i < n; i++)
    {
        int x,c;
        cin >> x >> c;
        add.push_back({x, c});
        
        alls.push_back(x);
    }
    // 对左右边界输入
    for(int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        
        alls.push_back(l);
        alls.push_back(r);
        
    }
    // 进行去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(),alls.end()), alls.end());
    // 遍历add
    for(auto item : add)
    {
        // 找到该值的位置
        int x = find(item.first);
        // 用数组存储该值,相当于在空数组上加上这个数字
        a[x] += item.second;
    }
    // 前缀和数组
    for(int i = 1; i <= alls.size(); i++)s[i] = s[i - 1] + a[i];
    
    for(auto item : query)
    {
        // 找到左右边界的位置
        int l = find(item.first), r = find(item.second);
        // 输出该段的和
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
    
}

注意:经过此过程,alls数组上只有要添加的值与区间的边界。

上面是c++的写法,通常在Java和Python中也可以自己实现这种去重的unique算法。可以采用双指针算法实现。

写一个迭代器数组,双指针判断,遍历数组,如果元素不是首数字且不和后一位相同,则记录在a[j]数组中。

注意是在同一个数组中操作的,但是可以保证去重数组长度始终小于等于原数组。最后返回a[0] ~ a[j - 1]即可。文章来源地址https://www.toymoban.com/news/detail-427862.html

vector<int>::iterator unique(vector<int> &a)
{
    int j = 0;
    for(int i = 0; i < a.size(); i++)
    {
        if(!i || a[i] != a[i - 1])
            a[j++] = a[i];
    }
    // 在a[0] ~ a[j - 1]有所有a中不重复的数
    return a.begin() + j;
}

到了这里,关于离散化及模板详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • spring 详解三 IOC(spring实例化及后处理器)

    Spring在容器初始化的时候,读取XMl配置,将其封装成 BeanDefinition(Bean定义)对象 ,描述所有bean的信息 BeanDefinition会 注册存储到beanDefinitionMap集合中 Spring框架 遍历beanDefinitionMap,使用反射创建Bean实例对象 创建好之后的对象 存储在singletonObjects的map集合中,当getBean时,从该map中

    2024年02月13日
    浏览(77)
  • 微服务系列文章 之SpringBoot之定时任务详解

    使用SpringBoot创建定时任务非常简单,目前主要有以下三种创建方式: 一、基于注解(@Scheduled) 二、基于接口(SchedulingConfigurer) 前者相信大家都很熟悉,但是实际使用中我们往往想从数据库中读取指定时间来动态执行定时任务,这时候基于接口的定时任务就派上用场了。 三、

    2024年02月16日
    浏览(37)
  • 微服务系列文章 之 nginx日志配置指令详解

    日志对于统计排错来说非常有利的。本文总结了nginx日志相关的配置如access_log、log_format、open_log_file_cache、log_not_found、log_subrequest、rewrite_log、error_log。 nginx有一个非常灵活的日志记录模式。每个级别的配置可以有各自独立的访问日志。日志格式通过log_format命令来定义。ngx_

    2024年02月16日
    浏览(48)
  • 微服务系列文章 之 Nginx状态监控日志分析详解

    1、Nginx状态监控 Nginx提供了一个内置的状态信息监控页面可用于监控Nginx的整体访问情况,这个功能由ngx_http_stub_status_module模块进行实现。 使用nginx -V 21 | grep -o with-http_stub_status_module命令检测当前Nginx是否有status功能,如果输出ngx_http_stub_status_module则说明是有的,如果没有可以

    2024年02月16日
    浏览(52)
  • 【C++系列P7】格式与实例化操作——[模板]详解

     前言 大家好吖,欢迎来到 YY 滴 C++系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁,主要内容含 目录 一.模板  1.函数模板 一.函数模板概念 二.函数模板的格式 三.函数模板的实例化  1.隐式实例化 2.显式实例化  3.模板参数的匹配原则  2.类模板 一.类模板的格式 二

    2024年02月10日
    浏览(42)
  • 【unity本站最全系列】unity常用API大全一篇文章足以(万字详解)不信你不收藏

    👨‍💻个人主页 :@元宇宙-秩沅 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 本文由 秩沅 原创 收录于专栏 unity 实战系列 ⭐相关文章⭐ ⭐【软件设计师高频考点暴击】 -本站最全-unity常用API大全(万字详解),不信你不收藏 -关于游戏剧情模式中用到的基础简单API -控制游

    2024年02月07日
    浏览(57)
  • 算法基础模板 快排、快选、归并、二分、离散化、区间合并、链表、图搜索、最短路等

    解决逆序对数量问题,即 if arr[i]arr[j]:res += mid - i + 1 时间复杂是 O ( n 2 + m ) O(n2+m) O ( n 2 + m ) , n n n 表示点数, m m m 表示边数 时间复杂度 O ( m l o g n ) O(mlogn) O ( m l o g n ) , n n n 表示点数, m m m 表示边数

    2024年02月13日
    浏览(43)
  • 【离散数学期复习系列】四、图

    1.无序积: 设A、B为两集合,称{{a ,b} | a ∈A∧b∈B}为A与B的无序积,记作AB.,将无序对{a ,b} 记作(a ,b),且(a ,b)=(b,a) 多重集:有重复元素的集合 2. (1)无向图: 一个无向图G是一个二元组〈V,E〉,其中 1)V是一个非空的有穷集合,称为.G的顶点集,V中元素称为顶点或结点; 2)E是无序积VV的一个

    2024年02月05日
    浏览(62)
  • 【离散数学期复习系列】六、树

    1.什么是树? 无向树(树):不含回路的连通无向图 森林:每个连通分支均是树的非连通无向图 平凡树:平凡图 树叶:树中度数为1的顶点 分支点:树中度数大于等于2的顶点,也就是根节点和内点 2.树的相关性质 设G=V,E,|V|=n,|E|=m,则下面各命题是等价的: (1)G连通且不含回路; (2)G的每对

    2024年02月01日
    浏览(34)
  • 【离散数学期复习系列】五、一些特殊的图

    1.二部图 (1)二部图(偶图): 若能将无向图G=V,E的顶点集V划分成两个不相交的非空子集V1和V2,使得G中任 何一条边的两个端点一个属于V1,另一个属于V2 ,则称G为二部图,V1,V2称为互补顶点子集,此时可将G记成G=V1,V2,E. (2)完全二部图: 若V1中每一个顶点与V2中每一个顶点均有且仅有一条边

    2024年02月09日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包