算法学习:离散化

算法学习:离散化

Banner 图源网络,侵删。

离散化

离散化:将无限空间中的有限个体映射到有限的空间中。

比如说我有一个无尽的坐标轴,上面有 $10^4$ 个点,每个点的坐标值可以很大很大接近无限。如果我想知道比其中一个点小的点有多少个,暴力比较每个点的坐标值则会因为数据过大而 Boom。而我们通过点与点相对关系,将点的值进行重新赋值,则可以大大减小算法的复杂度。

比如,我现在的数轴上只有6个点, 他们的坐标分别为 $0$、$610$、$10^5+2$、$99$、$5$、$10^9+45$,如果我只是按照他们原有的值进行比较,最大要比较到 $10^9+45$。而如果我们用他们的相对大小来进行比较,即转换为 $0$、$3$、$4$、$2$、$1$、$5$ 则会方便很多。这就是离散化的思想,就是将离散的事物进行重新分配

离散化方法:排序+二分

(推荐使用本方法)

基本原理就是排序后使用STL中的unque()函数来获取整体数据不同元素的个数,然后在已排序序列二分查找 $num[i]$ 的值,从而得到对 $num[i]$ 对应的值,然后进行重新赋值。

1
2
3
4
5
6
7
8
for(int i = 0; i < n; i++){
scanf("%d", &num[i]);
disc[i] = num[i]; // num:原数据数组,disc:离散化后的数组
}
sort(disc, disc + n);
cnt = unique(disc, disc + n) - disc; // STL中的unique函数,具体内容见👇
for(int i = 0; i < n; i++)
num[i] = lower_bound(disc, disc + n, num[i]) - disc;
  • unique(a, b)函数:STL中比较常见的函数,他的功能是“删除”序列中所有相邻的重复元素(只保留一个),因为只是处理相邻的重复元素所以在使用这个函数之前要进行排序。(此处略去更具体的都能再写一页博客的内容)。其中参数a,b为指针,类似sort()函数中的参数。
  • lower_bound(a, b, v)函数:二分查找返回ab指针之间空间中大于等于 $v$ 的第一个迭代器。

离散化方法:排序+暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define MAX_N 1e5+5 // 根据实际问题调整
struct Node{
int data;
int index;
}num[MAX_N];
bool cmp(Node a, Node b){
return a.data < b.data;
}
int rank[MAX_N], n;
int main(){
scanf("%d", &n);
for(int i = 0;i < n; i++){
scanf("%d", &num[i].data);
num[i].index = i;
}
sort(num, num + n, cmp);
for(int i = 1; i <= n; i++){
rank[num[i].id] = i;
}
return 0;
}

排序之后按照原顺序进行赋值,相同元素就会出现离散化不成同一元素的情况,所以不推荐这种方法。


听大佬说洛谷P1955是一道有关离散化的题,我这个蒟蒻还没有做。🙃

有时间做了再搞题解什么的。🙃

题解我搞出来了,传送门:🚪

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×