网页设计网站建设报告,建设厅网站举报,博客html模板,制作网站过程目录
1. 离散化的概念
1.1 离散化的运用思路
1.2 离散化的方法
1.2.1 排序 1.2.2 确定一个元素离散化后的结果
1.3 案例分析
1.3.1 1.3.2 区间和 #xff08;来源#xff1a;Acwing#xff09; 1. 离散化的概念 离散化#xff0c;把无限空间中有限的个体映射到有限的…目录
1. 离散化的概念
1.1 离散化的运用思路
1.2 离散化的方法
1.2.1 排序 1.2.2 确定一个元素离散化后的结果
1.3 案例分析
1.3.1 1.3.2 区间和 来源Acwing 1. 离散化的概念 离散化把无限空间中有限的个体映射到有限的空间中去以此提高算法的时空效率。 例如 原数据1,999,100000,15 处理后1,3,4,2 原数据{100,200}{20,50000}{1,400} 处理后{3,4}{2,6}{1,5} 1.1 离散化的运用思路
以下离散化均指整数保序的离散化。
根据离散化的定义我们能够发现需要如果数据需要做离散化的处理那么该数据的值域跨度是非常大的但是分布很稀疏。因为值域的跨度相当大自身并不能作为数组的下标保存对应的属性。但是如果只需要这些数据的相对属性那么就可以对数据进行离散化处理。
1.2 离散化的方法
这里只讲常用的方法重复元素离散化的结果相同。
我们只需要确保两个事情不变
首先保证离散化之后的数据尽可能地小而且非负。
其次离散后的数据要保持原本的大小关系原本相等的也要保持相等否则就是错误的离散。 因此找出原数据在序列中的序位 (可以直接理解为排第几) 就是离散化的关键。
1.2.1 排序
离散化就是确定找出原数据在序列中排第几嘛因此我们直接对其排序就好了排完序便可直接根据该数据所在位置的下标确定其离散化的结果。但是显然单单排序是不够的如果原数据中有重复元素那么相同的数据就会有不同的离散化结果这是不被允许的。因此对排好序的数组我们还要进行去重的操作。
假设原数组为 array。 对于C排序用sort去重用unique删除末尾重复的元素用erase即 array.erase(unique(array.begin(), array.end()), array.end()) 对于C语言用 qsort 排序用双指针算法去重就行。 1.2.2 确定一个元素离散化后的结果
比如将数据1 5 3 2 2 3进行排序去重删除后得到结果1 2 3 5比如我们想要知道 5 离散化后的结果是多少该怎么做呢答案就是二分查找哦。5 对应的下标就是 5 离散化的结果。这里就是标准的二分查找模板。 二分查找请参考http://t.csdn.cn/CVAGj int binary_search1(int* nums, int numsSize, int target)
{int l 0, r numsSize - 1;while (l r){int mid l r 1;if (nums[mid] target){r mid;}else{l mid 1;}}return l;
}
1.3 案例分析
1.3.1 题目描述 现有数列 A1A2A3 ··· An数列中可能有重复元素。现在要求输出该数列的离散化数列重复元素离散化后的数字相同。 输入 第一行一个整数 n (1 n 10 ^ 5) 第二行n个整数整数每个整数的取值为[-10^9, 10^9]。 输出 一行包括 n 个整数。表示数列对应的离散化数列重复元素离散化后的数字相同。 样例输入 6 1 23424 242 65466 242 0 样例输出 1 3 2 4 2 0 int binary_search1(vectorint nums, int target)
{int l 0, r nums.size() - 1;while (l r){int mid l r 1;if (nums[mid] target){r mid;}else{l mid 1;}}return l;
}int main()
{vectorint array;vectorint a;int n;cin n;int num;for (int i 0; i n; i){scanf(%d, num);array.push_back(num);a.push_back(num);}//排序sort(array.begin(), array.end());//去重和删除array.erase(unique(array.begin(), array.end()), array.end());for (int i 0; i a.size(); i){int ret binary_search1(array, a[i]);cout ret ;}cout endl;system(pause);return 0;
} 1.3.2 区间和 来源Acwing 假定有一个无限长的数轴数轴上每个坐标的数都是0. 现在我们首先进行 n 次操作每次操作将某一位置 x 上的数加上 c 。 接下来进行 m 次询问每个询问包含两个整数 l 和 r你需要求出在区间 [l, r] 之间所有数的和。 输入格式 第一行包含两个整数 n 和 m。 接下来 n 行包含两个整数 x 和 c。 再接下来 m 行每行包含两个整数l 和 r。 输出格式 共 m 行每行输出一个询问中所求的区间内数字和。 数据范围 -10 ^ 9 x 10 ^ 9 , 1 n , m 10 ^ 5 , -10 ^ 9 l r 10 ^ 9 , -10000 c 10000 const int N 300010;//这里用来存在c的位置加上x 和每一次询问的区间当然也可以用结构体
typedef pairint, int PI;//在x的位置加上c不止一次数组存
vectorPI add;
//询问的区间不止一次数组存
vectorPI query;
//存所有添加的值c需要离散化
vectorintalls;
//保存离散化后的结果
int a[N];
//求区间和会用到前缀和的创建一个前缀和数组
int s[N];int n, m;//这里离散化的值是从1开始的为了对应求前缀和时也是从1开始
int binary_search1(int target)
{int l 0, r alls.size() - 1;while (l r){int mid l r 1;if (alls[mid] target){r mid;}else{l mid 1;}}return l 1;
}int main()
{cin n m;for (int i 0; i n; i){int x, c;cin x c;//记录每一次添加的位置和值add.push_back({ x,c });//加上c的位置x是需要离散化的alls.push_back(x);}//m次询问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());for (pairint, int i : add){//将x位置加上c的x进行离散化int x binary_search1(i.first);//a数组中的下标就代表离散化的值哈值代表x的位置a[x] i.second;}//前缀和处理for (int i 1; i alls.size(); i){s[i] s[i - 1] a[i];}//处理询问for (pairint, int i : query){int l binary_search1(i.first);int r binary_search1(i.second);cout s[r] - s[l - 1] endl;}return 0;
}
