域名访问网站,慧聪网怎样做网站友情链接,深圳公司网站建设服务,厦门建设局刘以汉离散化
在C中#xff0c;离散化通常指的是将连续的数值或数据转化为离散的形式。这在数值分析、信号处理、图像处理和机器学习等领域都非常常见。以下是一些离散化的基本概念和方法#xff1a;
1.区间划分#xff1a;
将连续变量的值域分成多个区间#xff0c;每个区间对…离散化
在C中离散化通常指的是将连续的数值或数据转化为离散的形式。这在数值分析、信号处理、图像处理和机器学习等领域都非常常见。以下是一些离散化的基本概念和方法
1.区间划分
将连续变量的值域分成多个区间每个区间对应一个离散的值。例如将浮点数分成若干个区间可以用区间的中点、边界或其他代表值来替代该区间内的所有值。
2.量化
在信号处理中量化是将连续信号转换为离散信号的过程。可以使用固定点数表示或浮点数表示。
3.
插值与样本选择在离散化过程中可以通过插值技术生成离散样本或选择数据集中的特定样本点。 前缀和算法 二分查找
我们来看一道题可以帮助我们更好的理解这个算法 Acwing804.区间和 我们举个例子 我们现在根据题来看题中是进行了3次读操作3次写操作。
代码如下
#includeiostream
#includevector
#includealgorithm
using namespace std;const int N 300010;
int n, m; // n 表示插入操作的数量m 表示查询操作的数量
int a[N]; // 用于存储每个离散化后位置的值
int s[N]; // 前缀和数组
vectorint alls; // 用于存储所有需要离散化的坐标
vectorpairint, int add, query; // 分别存储插入操作和查询操作// 二分查找找到 x 在 alls 中对应的位置离散化
int find(int x)
{int l 0, r alls.size() - 1;while (l r){int mid l r 1;if (alls[mid] x) // 如果中间值大于等于 x右边界缩小r mid;else // 否则左边界增大l mid 1;}return r 1; // 返回离散化后的索引从 1 开始
}int main()
{// 读取插入操作和查询操作cin n m;for (int i 1; i n; i){int x, c;cin x c;alls.push_back(x); // 收集需要离散化的 x 坐标add.push_back({x, c}); // 保存插入操作} for (int i 1; i m; i){int l, r;cin l r;alls.push_back(l); // 收集查询范围的左端点alls.push_back(r); // 收集查询范围的右端点query.push_back({l, r}); // 保存查询操作}// 去重并排序完成离散化准备sort(alls.begin(), alls.end()); // 将所有的坐标排序alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去重/*unique 函数用于 移除相邻的重复元素它并不真正删除元素而是将重复的元素移动到容器的末尾部分函数返回一个迭代器该迭代器指向新容器末尾的下一个位置即去重后第一个“无效”元素的位置。前提条件为了让 unique 正确工作输入的容器必须是有序的即相等的元素必须相邻。因此在调用 unique 之前通常要先对容器进行排序sort。alls.begin() 是 alls 数组的起始位置。alls.end() 是 alls 数组的末尾位置不包括最后一个元素。unique(alls.begin(), alls.end()) 将相邻的重复元素移动到容器末尾并返回一个新的迭代器 new_end该迭代器指向去重后有效数据的末尾。*/// 处理插入操作for (auto item : add){int x find(item.first); // 找到 x 在离散化后的索引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); // 找到 l 在离散化后的索引int r find(item.second); // 找到 r 在离散化后的索引cout s[r] - s[l - 1] endl; // 输出区间 [l, r] 的和并换行}return 0;
}离散化代码源码
