网站导航
> 技术文档 > 进阶数据结构——离散化

进阶数据结构——离散化

网友: 技术文档 2025-07-30 21:57:50

目录

  • 一、离散化的核心思想与本质
  • 二、离散化的应用场景
  • 三、离散化的实现步骤
  • 四、离散化的复杂度分析
  • 五、离散化的优化技巧
  • 六、常见误区与调试技巧
  • 七、代码模版（c++）
  • 八、经典例题
    • 数列离散化
    • 寻找满足高度的最大山峦美丽值
  • 九、总结与学习建议

在这里插入图片描述

一、离散化的核心思想与本质

核心思想：离散化是一种将连续数据映射到有限离散值的技术，通常用于处理大规模数据或稀疏数据。
本质：通过将原始数据重新编号或映射，减少数据的规模和复杂度，同时保留数据的相对关系。

二、离散化的应用场景

区间查询与更新：

在线段树或树状数组中，离散化可以将大范围的坐标映射到小范围的索引，节省空间和时间。

示例：LeetCode 315. 计算右侧小于当前元素的个数。

统计与计数：

在统计频次或计数问题中，离散化可以减少数据规模，提高效率。

示例：LeetCode 493. 翻转对。

图论与网络流：

在图论问题中，离散化可以将大范围的节点编号映射到小范围，简化问题。

示例：LeetCode 685. 冗余连接 II。

几何问题：

在几何问题中，离散化可以将连续的坐标映射到离散的网格点，简化计算。

示例：LeetCode 850. 矩形面积 II。

三、离散化的实现步骤

  1. 数据收集
    收集所有需要离散化的数据点（如坐标、值等）。

  2. 排序与去重
    对数据点进行排序，并去除重复值。

  3. 映射与编号
    将原始数据点映射到离散的索引（通常从 0 或 1 开始）。

  4. 应用离散化
    使用映射后的索引代替原始数据点进行计算或存储。

四、离散化的复杂度分析

时间复杂度
排序与去重：
O(nlogn)，其中
n 是数据点的数量。

映射与编号：
O(n)。

空间复杂度
存储映射关系：
O(n)。

五、离散化的优化技巧

  1. 二分查找优化
    在映射过程中，使用二分查找快速确定数据点的离散索引。

  2. 动态离散化
    在动态数据流中，实时维护离散化映射。

  3. 多维度离散化
    在多维数据中，分别对每个维度进行离散化。

六、常见误区与调试技巧

  1. 误区一：离散化会丢失信息
    澄清：离散化仅改变数据的表示方式，不改变数据的相对关系。

  2. 误区二：离散化适用于所有问题
    澄清：离散化适用于数据范围大但数据点稀疏的问题，对于密集数据可能不适用。

  3. 调试方法
    打印映射关系：在离散化后输出映射关系，检查是否正确。

可视化数据分布：绘制原始数据和离散化后的数据分布，检查一致性。

七、代码模版（c++）

#include#include#includeusing namespace std;template<class T>class Dicretizer {private:vector<T>m_data;public:void addData(T v);void process();int getData(T v) const;int size()const;};template<class T>void Dicretizer<T>::addData(T v) {m_data.push_back(v);}template<class T>void Dicretizer<T>::process() {sort(m_data.begin(), m_data.end());int lastId = 0;for (int i = 1; i < m_data.size(); i++) {T t = m_data[i];if (t != m_data[lastId]) {m_data[++lastId] = t;}}while (lastId < m_data.size() - 1) {m_data.pop_back();}}template<class T>int Dicretizer<T>::getData(T v) const {int l = -1, r = m_data.size();while (l + 1 < r) {int mid = (l + r) / 2;if (m_data[mid] >= v)r = mid;else l = mid;}if (m_data[r] != v || r == m_data.size())return -1;return r;}template<class T>int Dicretizer<T>::size() const {return m_data.size();}int main() {return 0;}

八、经典例题

数列离散化

#include#include#includeusing namespace std;template<class T>class Dicretizer {private:vector<T>m_data;public:void addData(T v);void process();int get(T v) const;int size() const;};template<class T>void Dicretizer<T>::addData(T v) {m_data.push_back(v);}template<class T>void Dicretizer<T>::process() {sort(m_data.begin(), m_data.end());int lastId = 0;for (int i = 1; i < m_data.size(); i++) {T x = m_data[i];if (x != m_data[lastId]) {m_data[++lastId] = x;}}while (lastId < m_data.size() - 1) {m_data.pop_back();}}template<class T>int Dicretizer<T>::get(T v) const {int l = -1, r = m_data.size();while (l + 1 < r) {int mid = (l + r) / 2;if (m_data[mid] >= v)r = mid;else l = mid;}if (r == m_data.size() || m_data[r] != v)return -1;return r;}template<class T>int Dicretizer<T>::size() const {return m_data.size();}int a[100001];int main() {int n;cin >> n;while (n--) {int s;cin >> s;Dicretizer<int> d;for (int i = 0; i < s; i++) {int x;cin >> x;a[i] = x;d.addData(x);}d.process();for (int i = 0; i < s; i++) {cout << d.get(a[i]) + 1 << \' \';//因为数组下标是从0开始,所以加一}cout << endl;}return 0;}

寻找满足高度的最大山峦美丽值

这道题太恶心了，实在不懂也没关系。

#include#include#includeusing namespace std;template<class T>class Dicretizer {private:vector<T>m_data;public:void addData(T v);void process();int getData(T v) const;int size()const;};template<class T>void Dicretizer<T>::addData(T v) {m_data.push_back(v);}template<class T>void Dicretizer<T>::process() {sort(m_data.begin(), m_data.end());int lastId = 0;for (int i = 1; i < m_data.size(); i++) {T t = m_data[i];if (t != m_data[lastId]) {m_data[++lastId] = t;}}while (lastId < m_data.size() - 1) {m_data.pop_back();}}template<class T>int Dicretizer<T>::getData(T v) const {int l = -1, r = m_data.size();while (l + 1 < r) {int mid = (l + r) / 2;if (m_data[mid] >= v)r = mid;else l = mid;}if (m_data[r] != v || r == m_data.size())return -1;return r;}template<class T>int Dicretizer<T>::size() const {return m_data.size();}#define maxn 200001struct HB {int h, b;}hb[maxn];int k[maxn], maxv[maxn];//k作为询问数组，maxv代表限高的最大美丽值bool cmp(const HB& a, const HB& b) {return a.h < b.h;}int main() {Dicretizer<int>d;int n, q;cin >> n >> q;for (int i = 0; i < n; i++) {cin >> hb[i].h;d.addData(hb[i].h);}for (int i = 0; i < n; i++) {cin >> hb[i].b;}for (int i = 0; i < q; i++) {cin >> k[i];d.addData(k[i]);}d.process();for (int i = 0; i < n; i++) {hb[i].h = d.getData(hb[i].h);}for (int i = 0; i < q; i++) {k[i] = d.getData(k[i]);}sort(hb, hb + n, cmp);maxv[d.size()] = -1;int j = n - 1;for (int i = d.size() - 1; i >= 0; i--) {maxv[i] = maxv[i + 1];while(j >= 0 && hb[j].h == i) {if(hb[j].b > maxv[i]) {maxv[i] = hb[j].b;}j--;}}for (int i = 0; i < q; i++) {int x = k[i];cout << maxv[x] << endl;}return 0;}

九、总结与学习建议

  1. 核心总结
    离散化是一种将连续数据映射到离散值的技术，适用于处理大规模或稀疏数据。

通过排序、去重和映射，可以高效实现离散化。

  1. 学习建议
    分类刷题：按问题类型集中练习（如区间查询、统计计数、几何问题）。

理解算法原理：掌握离散化的实现步骤和优化技巧。

手写模拟过程：在纸上模拟离散化的过程，加深直观理解。

在这里插入图片描述
希望大家可以一键三连，后续我们一起学习，谢谢大家！！！
在这里插入图片描述

网络标签：

相关问题