离散化模板

发表于 | 更新于 | 分类于

离散化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 4;
int a[N];			//原本数组 
int ls[N];		//离散化后的数组 
int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++)
	{
		cin >> a[i];
		ls[i] = a[i];			//对原数组进行备份 
	}
	sort(ls, ls + n);		//对原数组(即备份数组进行排序)
	int len = unique(ls, ls + n) - ls; 		//进行去重减少离散长度(避免出现原数组1 1 2 2 离散为1 1 3 3的情况)
	for(int i = 0; i < n; i ++)
		a[i] = lower_bound(ls, ls + len, a[i]) - ls + 1;			//将原数组进行离散化记录排序下标(即离散化) ，在有效长度len中进行搜索映射
	for(int i = 0; i < n; i ++)
		cout << a[i] << " ";
	puts("");
	return 0;
}
0%