c++算法之离散化-Toy模板网

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

什么是离散化？

　　离散化，故离散数学，其中的“离散”就是不连续的意思。离散化可以保持原数值之间相对大小关系不变的情况下将其映射成正整数。

也就是给可能用到的数值按大小关系分配一个编号，来代替原数值进行各种操作。

离散化步骤：

1.排序

2.去重

3.归位

举一个例子：

将{4000，201,11,45,830}离散为{5,4,3,2,1}：

1     4000 201 11 45 830
2        1      2   3  4  5
3      sort:
4 离散  11 45 201 830 4000
5        3      4  2   5    1
6 编号      1   2  3   4    5
7                   
8 a[1~n]:[5]  [3] [1] [2]  [4]

既然讲了这么多，是时候上代码了：

1.去重离散

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int a[101100],b[101100];
 5 int main(){
 6     int n;
 7     cin >> n;
 8     for(int i=1;i<=n;i++){
 9         cin >> a[i];//未排序 
10         b[i]=a[i];//副本 
11     }
12     sort(b+1,b+n+1);
13     int cnt=unique(b+1,b+n+1)-(b+1);//去重函数unique
14     for(int i=1;i<=n;i++){
15         //二分查找函数lower_bound():>=a[i]的地址，“-b”就可以返回编号
　　　　　　//这里注意：减去的b可不是b的数值，是b的地址 
16         a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
17         printf("%d ",a[i]);
18     } 
19     return 0;
20 }

2.不去重离散

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int a[101100],b[101100]
 5 int main(){
 6     int n;
 7     cin >> n;
 8     for(int i=1;i<=n;i++){
 9         cin >> a[i].x;//未排序 
10         a[i].y=a[i].x;//副本 
11     }
12     sort(b+1,b+n+1);
13     for(int i=1;i<=n;i++){
14         //二分查找函数:>=a[i]的地址，“-b”就可以返回编号 
15         a[i]=lower_bound(b+1,b+n+1,a[i])-b;
16         printf("%d ",a[i]);
17     } 
18     return 0;
19 }