离散化

字数

527 字

阅读时间

3 分钟

---

什么时候会用到离散化？

当题目所给范围很大，但我们实际用到的范围很小（如：题目所给数据范围是1~1e9，但我们实际使用的数据范围是1~1e6，此时就可以用离散化，将我们用到的数据都映射到更小的数据范围）

怎么离散化？

步骤： 需要保序：保存数组，排序，判重，二分 不需要保序：使用 map 容器，或者使用 hash表

写法：

有序的离散化

int a[N], b[N]；
for (int i = 1; i <= n; i ++)
	cin >> a[i];
memcpy(b, a, sizeof a); // 将 a 数组中的数据都复制到 b 数组中，用于离散化
sort(b + 1, b + n + 1); // 将 b 数组从小到大排序

int bend = unique(b + 1, b + n + 1) - (b + 1); // bend 是 b 数组去重后剩下的数的个数

for (int i = 1; i <= n; i ++)
{
	// lower_bound(begin, end, res)：begin指的是数组开始的位置，end指的是数组结束位置的下一位，res 指的是要查询的数的大小
	// lower_bound() 会返回指定数组范围内第一个大于等于 res 的数
	// upper_bound() 会返回指定数组范围内第一个大于 res 的数
	// 如果没找到，则会返回 end() 的地址
	int x = lower_bound(b + 1, b + 1 + bend, a[i]) - b; // 输出结果的排序从 1 开始(若要从 0 开始，则lower_bound() - (b + 1) ) 
}

即：将数组a: 9 25 77 62 98 77 去重并离散化后，变为 b : 1 2 4 3 5 4

无序的离散化

需要注意的是，若在数据量过大时，使用unordered_map，可能会被卡常

int n = 0;
unordered_map<int, int> g;

int get(int x) // 离散化，返回离散化所属
{
	if (g.count(x) == 0) // 没找到对应的值，则将其加入到离散化数组中
		g[x] = ++ n; // 离散化数组从 1 开始
	return g[x]; // 返回离散化结果
}

贡献者

freeway348

文件历史

最后编辑于 4 天前查看完整历史

e587f-Update 简介梗概.md