【算法笔记】离散化

1 离散化

离散化(Discretization)：就是把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。「1」

离散化本质上可以看成是一种哈希 ，其保证数据在哈希以后仍然保持原来的全/偏序关系。
通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。
用来离散化的可以是大整数、浮点数、字符串……等等。「2」

原数据：(1,999,100000,15)

处理后：(1,3,4,2)

原数据：{100,200},{20,50000},{1,400}

处理后：{3,4},{2,6},{1,5}

1.1 离散化模板

模板1：使用vector

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
vector<int>v;
int a[N];

int find(int f){
	//二分模板
	int l=0,r=v.size()-1;
	while(l<r){
		int mid=(l+r)/2;
		if(v[mid]>=f) r=mid;
		else l=mid+1;
	}
	return r+1; 
}

int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		v.push_back(a[i]);
	}
	sort(v.begin(),v.end());//排序
	v.erase(unique(v.begin(),v.end()),v.end());
	//因为unique只能把重复元素放在后面，所以要用erase删除后面的元素
	for(int i=1;i<=n;i++) cout<<find(a[i]);//用二分查找离散值
}

模板2：使用map

因为map会自动去重和排序，而且可以使用数组下标，所以比较方便。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int a[N];
map<int,int>M;//map容器
int n;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		M[a[i]]=0;//把离散化的值加入map
	}
	int cnt=0;
	for(auto it:M) it.second=cnt++;//可以用auto直接迭代stl容器
	for(int i=1;i<=n;i++) cout<<M[a[i]]<<" ";
}

1.2 经典例题

(acwing802区间和)

1.2.1 题目大意

很显然，这是一道前缀和的题，但是数据太大（$10^9$），所以需要用到离散化。

#include<bits/stdc++.h>
using namespace std;
vector<int>v;
vector<pair<int,int>>x,y;
 
int a[300100]={0},s[300100]={0};

int find(int f){
	int l=0,r=v.size()-1;
	while(l<r){
		int mid=(l+r)/2;
		if(v[mid]>=f) r=mid;
		else l=mid+1;
	}
	return r+1; 
}

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	while(n--){
		int l,c;
		scanf("%d%d",&l,&c);
		x.push_back({l,c});
		v.push_back(l);
	}
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		y.push_back({l,r});
		v.push_back(l);
		v.push_back(r);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(auto it:x){
		int t=find(it.first); 
		a[t]+=it.second;
	}
	for(int i=1;i<=v.size();i++) s[i]=s[i-1]+a[i];
	for(auto it:y){
		int l=find(it.first),r=find(it.second); 
		printf("%d\n",s[r]-s[l-1]);
	}
	return 0;
}

引用文献

「1」百度百科离散化

「2」离散化(补充）