写点什么

算法基础:离散化及模板详解

作者:timerring
  • 2022-11-15
    山东
  • 本文字数:3128 字

    阅读完需:约 10 分钟

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

🔥本文已收录于算法基础系列专栏: 算法基础教程 欢迎订阅。


离散化

基本思想

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


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

算法思路

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



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


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 行,每行输出一个询问中所求的区间内数字和。


数据范围


,,,


输入样例


3 31 23 67 51 34 67 8
复制代码


输出样例


805
复制代码

题目分析

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


  • 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 53 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]即可。


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;}
复制代码


发布于: 刚刚阅读数: 3
用户头像

timerring

关注

还未添加个人签名 2022-07-14 加入

还未添加个人简介

评论

发布
暂无评论
算法基础:离散化及模板详解_算法_timerring_InfoQ写作社区