c++离散化处理大范围和重复数据

• 2020 年 5 月 17 日
• 筆記
• 算法

关于离散化

　　有些新手可能会问：离散化是什么？离散化就是将无限空间中有限的个体映射到有限的空间里去。

　　上面的定义肯定会有人看不懂（其实我刚开始学的时候也看不懂）

　　用我自己的话来说，就是在不改变数据的相对大小的条件下，对数据进行相应的压缩

　　可能还是有人看不懂，没关系，我们来看一个例子，顺便来讲一下离散化的基本操作：

　　现有一个数组：1，100，2367，562，364737，19，1974832947，100，562，2367

　　如果按照正常的方法，该开1974832947的空间，但是经过离散化后，就不需要

　　那么step 1：排序

　　用上面的例子来说，就是将上面的数据排序并去重，得到下面这组数据：

　　1，19，100，100，562，562，2367，2367，364737，1974832947

　　然后step 2：通过unique去重使大小与下标对应，并得到去重后的长度，得到下面这组数据：

　　1，19，100，562，2367，364737，1974832947

　　接着step 3：通过lower_bound算出离散化后的排列，得到下面这组数据：

　　1，2，3，4，5，6，7

　　那么这里就很尴尬了，这组数据无法应用于初始数据

　　所以在开始，我们多定义1个数组，来记录初始情况下的数据，再用step 3与其进行对应。

　　最终得到答案：1，3，5，4，6，2，7，3，4，5

　　下面给出模板：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[100005],b[100005],n;
 4 int main()
 5 {
 6     ios::sync_with_stdio(false);
 7     cin.tie(0);
 8     cin>>n;
 9     for(int i=1;i<=n;i++)
10     {
11         cin>>a[i];
12         b[i]=a[i];
13     }
14     sort(a+1,a+n+1);
15     int len=unique(a+1,a+n+1)-a-1;
16     for(int i=1;i<=n;i++)
17         b[i]=lower_bound(a+1,a+len+1,b[i])-a;
18     for(int i=1;i<=n;i++) cout<<b[i]<<" ";
19     return 0;
20 }

View Code