离散化

字数

271 字

阅读时间

2 分钟

---

什么时候会用到离散化？

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

怎么离散化？

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

写法：

有序的离散化

无序的离散化

需要注意的是，若在数据量过大时，使用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 天前查看完整历史

6442b-WWWW