离散化

Async #2.0.1

2026-05-05 12:04:30

发布于：浙江

2阅读

0回复

0点赞

离散化=

第一章：基本概念与原理

1.1 什么是离散化？

离散化是一种将取值空间很大但数量有限的数值映射到连续小整数的技术，保持原始数据间的相对大小关系。

数学定义：
设原数据集为：

$S = \{x_1, x_2, \dots, x_n\}, \quad x_i \in \mathbb{R}$

离散化映射为：

$f: S \rightarrow \{1, 2, \dots, m\}, \quad m \leq n$

满足保序性：

$\forall x_i, x_j \in S, \quad x_i < x_j \Rightarrow f(x_i) < f(x_j)$

1.2 为什么需要离散化？

实际问题场景：

输入数据：
[-1000000000, 3, 1000000000, 3, -999999999]
值域跨度：约20亿
但只有4个不同的值

问题：
1. 无法用数组直接存储（下标太大）
2. 树状数组、线段树等需要小下标
3. 很多算法要求连续小整数

解决方案：离散化
映射结果：[-1000000000→1, -999999999→2, 3→3, 1000000000→4]
离散化后：[1, 3, 4, 3, 2]
值域：1-4，只有4个不同值

1.3 应用场景

统计类问题：求区间内不同数的个数
离线查询：处理大量区间查询
数据结构：树状数组、线段树的前置处理
排序优化：减少比较开销
哈希替代：用整数代替大数值

第二章：离散化算法步骤

2.1 完整流程图

graph TD
    A[开始: 原始数组a] --> B[复制到临时数组t]
    B --> C[对t排序: sort(t)]
    C --> D[对t去重: unique(t)]
    D --> E[得到唯一值数组t_unique]
    E --> F[遍历原数组a]
    F --> G[在t_unique中二分查找a[i]]
    G --> H[得到下标idx]
    H --> I[映射: r[i] = idx + 1]
    I --> J[保存到结果数组r]
    J --> K[结束: 离散化完成]

2.2 示例演示

原始数据: a = [1000, 20, 1000, 500, 20, 3000]

步骤1: 复制
       t = [1000, 20, 1000, 500, 20, 3000]

步骤2: 排序
       t = [20, 20, 500, 1000, 1000, 3000]

步骤3: 去重
       t_unique = [20, 500, 1000, 3000]
       去重后长度 m = 4

步骤4: 建立映射表
       值   → 下标(+1)
       20   → 1
       500  → 2
       1000 → 3
       3000 → 4

步骤5: 应用映射
       a[0]=1000 → 在t_unique中是第3个 → 3
       a[1]=20   → 在t_unique中是第1个 → 1
       a[2]=1000 → 在t_unique中是第3个 → 3
       a[3]=500  → 在t_unique中是第2个 → 2
       a[4]=20   → 在t_unique中是第1个 → 1
       a[5]=3000 → 在t_unique中是第4个 → 4

结果: r = [3, 1, 3, 2, 1, 4]
验证: 保持相对大小关系 ✓

第三章：C++实现代码详解

3.1 方法一：STL标准库版（最常用）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int a[N];
int t[N];
int r[N];
void d(){
    for(int i=0;i<n;i++)t[i]=a[i];
    sort(t,t+n);
    int m=unique(t,t+n)-t;
    for(int i=0;i<n;i++){
        r[i]=lower_bound(t,t+m,a[i])-t+1;
    }
}

代码说明：

变量	含义	作用
`n`	数据个数	输入数据的数量
`a[]`	原始数组	存储待离散化的原始数据
`t[]`	临时数组	用于排序和去重的副本
`r[]`	结果数组	存储离散化后的值
`m`	唯一值数量	去重后不同元素的数量

关键函数：

sort(t, t + n)
- 对数组t的[0, n)范围排序
- 时间复杂度：O(n log n)
- 必须排序，因为unique和lower_bound都需要有序数组
unique(t, t + n)
- 将相邻重复元素移到末尾
- 返回新的"逻辑末尾"指针
- 示例：[1,1,2,2,3] → 处理后[1,2,3,1,2]，返回指向第二个3的指针
- 必须配合sort使用，只能处理相邻重复
lower_bound(t, t+m, val)
- 二分查找第一个≥val的位置
- 要求数组有序
- 返回指针，减去t得到下标
- 时间复杂度：O(log m)

为什么+1？

下标从0开始，但很多问题中从1开始更方便
树状数组通常从1开始
从0开始：r[i] = idx
从1开始：r[i] = idx + 1

3.2 方法二：手写函数版（理解原理）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int a[N];
int t[N];
int r[N];
int u(int l,int h){
    int k=0;
    for(int i=l;i<h;){
        int j=i+1;
        while(j<h&&t[j]==t[i])j++;
        t[k++]=t[i];
        i=j;
    }
    return k;
}
int b(int x,int m){
    int l=0,h=m-1;
    while(l<=h){
        int mid=(l+h)/2;
        if(t[mid]>=x)h=mid-1;
        else l=mid+1;
    }
    return l;
}
void f(){
    for(int i=0;i<n;i++)t[i]=a[i];
    sort(t,t+n);
    int m=u(0,n);
    for(int i=0;i<n;i++){
        r[i]=b(a[i],m)+1;
    }
}

函数说明：

u(int l, int h) - 手写去重函数
- 参数：l起始位置，h结束位置（不包含）
- 原理：双指针法
- k：写入位置，i：读取位置
- 跳过所有重复元素，只保留第一个
- 时间复杂度：O(n)
b(int x, int m) - 手写二分查找
- 参数：x查找的值，m数组长度
- 返回：第一个≥x的位置
- 原理：标准二分查找
- 时间复杂度：O(log m)

算法流程：

1. 复制: t = a
2. 排序: sort(t)
3. 去重: m = u(0,n)  // 得到唯一值个数
4. 离散化: 对每个a[i]，用二分查找在t[0..m-1]中位置
5. 映射: r[i] = 位置 + 1

3.3 方法三：结构体版（保留原始索引）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
struct P{
    int v;
    int i;
}p[N];
int a[N];
int r[N];
int n;
bool cmp(P x,P y){
    return x.v<y.v;
}
void g(){
    for(int i=0;i<n;i++){
        p[i].v=a[i];
        p[i].i=i;
    }
    sort(p,p+n,cmp);
    int k=1;
    for(int i=0;i<n;i++){
        if(i>0&&p[i].v!=p[i-1].v)k++;
        r[p[i].i]=k;
    }
}

结构体方法特点：

优点：
- 保留原始索引
- 一次排序完成
- 逻辑清晰

结构体定义：

struct P {
    int v;  // 值
    int i;  // 原始下标
};