CC++ & Algorithm

离散化——给数据“压缩打包”

中等7
语言版本：C++
概述：当数据范围很大但数量很少时，离散化可以把它们映射到连续的整数，像把家里所有玩具的尺寸按从小到大编号一样。

离散化：给大数据“瘦身”的小技巧

想象你在操场上玩“找朋友”游戏，老师给了你一张写着100个同学学号的纸条，但学号是1到100000之间随机的数，比如：100、50000、200、100、99999……虽然学号范围很大，但只有100个同学。如果直接用学号当数组下标，数组需要开100000个位置，太浪费了。离散化就像把这些学号重新“编号”：按大小排序后，最小的学号变成1，第二小的变成2……这样我们只需要一个大小为100的数组就能搞定所有数据。离散化的核心思想是：将范围大但数量少的数据映射到连续的整数上，节省空间、加快运行速度。

1. 什么是离散化？为什么要用它？

离散化是一种“压缩”技巧。当数据只关心它们之间的相对大小（谁大谁小、谁在哪两个之间），而不关心具体数值时，我们就可以把原本稀疏的大数字换成紧凑的、连续的整数（比如0,1,2,3...）。这样原本需要开一个巨大数组（比如2000000）的问题，变成了只需要开一个很小的数组（比如N个数，开N大小）。

生活例子：

  • 考试成绩排名：全班50人，分数可能是0~100的任意整数（甚至带小数）。排名时，我们只关心分数的高低顺序，不需要知道具体分数。离散化后，最高分变成排名1，次高分变成2……这样一来，用数组下标就能直接表示名次，非常方便。
  • 游戏里的段位：王者荣耀里的“荣耀战力”有时是几万，但玩家只有几百万个，离散化后把战力值映射成1~N的编号，就能快速判断某个战力在所有玩家中的位置。

2. 离散化的三个核心步骤

无论数据是什么，离散化都遵循以下三个步骤：

  1. 排序：把所有需要离散化的原始值从小到大排序。
  2. 去重：去掉重复的值（因为重复的值应该被映射到同一个编号）。
  3. 映射：对于每个原始值，在排序去重后的数组里用二分查找找出它的位置（下标），这个下标就是它新的“编号”。

下面我们用一个具体例子演示：假设有原始数据 [100, 500, 200, 100, 300]。

  • 排序：[100, 100, 200, 300, 500]
  • 去重：[100, 200, 300, 500]（注意重复的100只留一个）
  • 映射：
    • 100 在去重数组中的下标是 0（从0开始）
    • 200 的下标是 1
    • 300 的下标是 2
    • 500 的下标是 3 所以离散化后的新序列为：[0, 3, 1, 0, 2]。

3. C++实现：从代码到注释

下面是一个完整的程序，每一步都有详细的中文注释，方便理解。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 1. 原始数据（假设是一组很大的坐标）
    vector<int> original = {100, 500, 200, 100, 300};   // 原始数据：可能有重复

    // 2. 拷贝一份，用于排序和去重
    vector<int> sorted = original;                     // 复制原始数据

    // 3. 排序：让相同值靠在一起
    sort(sorted.begin(), sorted.end());               // 排序后：100,100,200,300,500

    // 4. 去重：unique将重复元素移到末尾，erase删除它们
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); // 去重后：100,200,300,500

    // 5. 离散化：用 lower_bound 二分查找每个原始值在sorted中的位置
    vector<int> disc;                                 // 存放离散化后的编号
    for (int val : original) {                       // 遍历原始数据的每个值
        // lower_bound返回第一个 >= val 的迭代器，减去sorted.begin()得到下标
        int id = lower_bound(sorted.begin(), sorted.end(), val) - sorted.begin();
        disc.push_back(id);                          // 将这个下标加入结果
    }

    // 6. 输出结果
    cout << "原始数据：";
    for (int v : original) cout << v << " ";
    cout << "\n离散化后：";
    for (int d : disc) cout << d << " ";
    // 输出：原始数据：100 500 200 100 300
    //       离散化后：0 3 1 0 2
    return 0;
}

代码关键点说明：

  • unique 函数会把相邻重复的元素移到末尾，并返回一个新末尾的迭代器，然后用 erase 把多余的部分删除。注意：必须先排序才能使用 unique。
  • lower_bound 返回的是第一个不小于给定值的迭代器。因为我们在排序去重后的数组里，原始值一定存在（因为是从原数据来的），所以它会找到该值对应的位置。减去 sorted.begin() 就得到了下标（从0开始）。

4. 新手最容易犯的4个错误

错误现象原因正确做法
使用 unique 前忘记排序unique 只能去掉相邻重复，如果没排序，重复值隔开就无法去重一定要先 sort 再 unique
去重后忘记 eraseunique 只是把重复值移到后面，并没有真正删除，导致 sorted 数组长度不变用 sorted.erase(unique(...), sorted.end()) 删除多余元素
用 find 代替 lower_bound 找位置find 是线性查找，时间复杂度O(n)，整体会退化成O(n²)一定要用 lower_bound（二分查找），复杂度O(log n)
映射时下标从1开始还是0开始搞混有些题目要求编号从1开始，有些从0开始，需要灵活处理根据题目要求，映射时加上偏移量（例如 id+1）

举个错误例子：如果不用 lower_bound，而是用 find 遍历去重数组：

int id = find(sorted.begin(), sorted.end(), val) - sorted.begin(); // 错误！太慢

当数据量很大（比如10^5个），线性查找会导致程序超时。所以一定要用二分查找。

5. 一个更贴近生活的完整示例：身高排名

假设学校有5个同学，他们的身高（单位：厘米）分别是 [156, 180, 156, 170, 165]。我们需要给每个身高一个“排名编号”，但只关心相对大小，不关心具体数值。用离散化可以轻松完成。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 原始身高数据
    vector<int> height = {156, 180, 156, 170, 165};   // 身高（厘米）

    // 复制一份并排序去重
    vector<int> uniqueHeight = height;                // 复制
    sort(uniqueHeight.begin(), uniqueHeight.end());   // 排序
    uniqueHeight.erase(unique(uniqueHeight.begin(), uniqueHeight.end()), 
                       uniqueHeight.end());           // 去重

    // 离散化：每个身高变成它在有序不重复数组中的下标
    vector<int> rank;                                 // 存储排名编号
    for (int h : height) {
        int id = lower_bound(uniqueHeight.begin(), uniqueHeight.end(), h) 
                 - uniqueHeight.begin();
        rank.push_back(id);                           // 下标从0开始
    }

    // 输出
    cout << "身高（厘米）：";
    for (int h : height) cout << h << " ";
    cout << endl;
    cout << "排名编号（从0开始）：";
    for (int r : rank) cout << r << " ";
    // 输出：身高：156 180 156 170 165
    //       排名：0 3 0 2 1
    // 说明：156最矮编号0，165编号1，170编号2，180最高编号3
    return 0;
}

6. 离散化在算法竞赛中的常见应用

  • 树状数组 / 线段树：当坐标范围很大（比如10^9）但实际需要操作的坐标点很少时，先离散化再建树，可以大幅度减少空间。
  • 区间求和：比如“给N个区间，每个区间覆盖一大段范围，但端点值很多且分散”，离散化端点后可以用差分数组扫描。
  • 并查集：如果元素编号是分散的大整数（如身份证号），离散化后再用并查集处理关系。

小练习：试着用离散化解决下面的问题：

有10000个学生的学号，分布在1~10^9之间，现在要把他们按学号从小到大分组，每组人数不超过K。如何用离散化快速得到每组学号的区间？

7. 相关知识点指引

  • 二分查找：lower_bound 和 upper_bound 是离散化映射的关键，建议彻底掌握。
  • unique去重原理：了解 STL 中 unique 的“相邻去重”机制，以及为什么需要先排序。
  • 坐标压缩：离散化是坐标压缩的一种形式，用在二维平面问题中（比如扫描线法）也很常见。
  • STL容器：熟练使用 vector、sort、unique、lower_bound，这些是离散化的基础工具。

离散化就像给数据“打标签”，把原本混乱的大数字变成整齐的小编号。下次当你面对“数值范围巨大但数量稀少”的问题时，不妨先试试这个技巧——说不定能让你的程序又快又省内存！

例题精讲

1单选题

离散化最适用于以下哪种场景？

A需要处理的数据范围极大，但数据个数相对较少
B数据范围较小，但数据个数非常多
C数据本身就是连续整数
D需要保留数据间的相对大小关系，且数据范围适中
2判断题

离散化处理后，原数据之间的相对大小关系会被破坏。

3填空题
给定一个数组 a，请将其离散化（映射到从1开始的连续整数），将结果存入b数组。要求去重。
int n; cin>>n;
vector<int> a(n), b;
for(int i=0;i<n;i++) cin>>a[i];
// 复制并排序
vector<int> tmp = a;
sort(tmp.begin(), tmp.end());
// 去重
tmp.erase(___(1)___, tmp.end());
for(int i=0;i<n;i++){
    // 二分查找获取离散化后的值（从1开始）
    b.push_back(___(2)___);
}
4单选题

对于原始数据 [100, 1000, 100, 500, 2000]，离散化后的结果是（假设映射为从1开始的连续整数且保持原有顺序的相对大小）：

A[1,3,1,2,4]
B[1,2,1,2,3]
C[1,4,1,3,5]
D[2,4,2,3,5]
5填空题
使用离散化辅助，统计数组 a 中逆序对的数量。以下是利用树状数组的代码片段，请补充离散化部分。
int n; cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
// 离散化
vector<int> tmp = a;
sort(tmp.begin(), tmp.end());
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
vector<int> disc(n);
for(int i=0;i<n;i++){
    disc[i] = ___;
}
// 树状数组求逆序对
BIT bit(tmp.size()+1);
long long ans = 0;
for(int i=n-1;i>=0;i--){
    ans += bit.query(disc[i]-1);
    bit.add(disc[i], 1);
}