中等C++7 分钟2,375 字

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

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

想象你在操场上玩“找朋友”游戏,老师给了你一张写着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++实现:从代码到注释

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

cpp
#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
去重后忘记 erase unique 只是把重复值移到后面,并没有真正删除,导致 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 遍历去重数组:

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

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


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

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

cpp
#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,这些是离散化的基础工具。

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

同类知识点