离散化

概念讲解

什么是离散化？

将值域大但数量少的数据映射到连续的小值域。

适用场景

  • 值域大（如 10^9），但只有 10^5 个数
  • 需要用数组下标访问

实现

12345678910vector<int> discretize(vector<int>& a) {
    vector<int> sorted = a;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    return sorted;
}

int getIndex(vector<int>& sorted, int x) {
    return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
}

考点分析

初赛考查方式

  1. 程序阅读： 离散化程序
  2. 编程题： 值域压缩

常见考点

  • 离散化实现
  • 配合树状数组
  • 配合线段树

例题精讲

例题 1：离散化

题目： 将 {100, 500, 1000, 50, 500} 离散化。

解答：

排序去重：{50, 100, 500, 1000}

映射：50→0, 100→1, 500→2, 1000→3

练习题

  1. 离散化的作用是什么？
查看答案

离散化的作用是将值域大但数量少的数据映射到连续的小值域。

例如：值域 10910^9，但只有 10510^5 个数，离散化后值域变为 10510^5。

这样就可以用数组下标访问，配合树状数组、线段树等数据结构使用。

  1. 如何实现离散化？
查看答案

离散化的实现：

  1. 排序：将所有值排序
  2. 去重：去除重复值
  3. 映射：用 lower_bound 查找下标
12345vector<int> sorted = a;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

int index = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
  1. 离散化的时间复杂度是多少？
查看答案
  • 排序：O(nlog⁡n)O(n \log n)
  • 去重：O(n)O(n)
  • 单次查找：O(log⁡n)O(\log n)

总复杂度：O(nlog⁡n)O(n \log n)

易错点

⚠️ 注意：

  1. 要先排序再去重
  2. 用 lower_bound 查找下标
  3. 下标从 0 还是 1 开始要统一
  4. 离散化后值域变小