离散化（discretization）详解：概念、实现与应用

创作时间:

作者:

@小白创作中心

离散化（discretization）详解：概念、实现与应用

引用

CSDN

https://blog.csdn.net/qq_72141173/article/details/146693328

离散化是一种重要的数据处理技巧，通过将分布稀疏的数据映射到更密集的范围内，可以显著提高算法的时空效率。本文将详细介绍离散化的概念、实现方法及其在实际问题中的应用。

离散化的概念

离散化是指将无限空间中的有限个体映射到有限空间中，以此提高算法的时空效率。在某些场景下，数据的绝对值并不重要，而相对大小才是关键。例如，对学生考试成绩进行排名时，我们并不关心具体的分数，而是关注排名顺序。

"离散化"的核心思想是用数字的相对值替代绝对值，将分布稀疏的数据转换为密集分布，从而让算法运行得更快、更节省空间。

离散化的步骤大致分为三步：

排序
离散化
归位

离散化是程序设计中常用的技巧之一，可以有效降低时间复杂度。其基本思想是在众多可能的情况中，只考虑实际需要的值。掌握这个思想需要通过大量题目来理解其特点。例如，在建造线段树时，如果空间不足，可以考虑使用离散化。

离散化的编码实现

给定的数列中经常包含重复的数据，因此一般有两种方法来进行离散化。重复数字在必要时可以去重，再进行离散化。对于不去重的情况，有以下两种方式来实现。

方法一：重复数据离散化为相同数据

nums = list(map(int, input().split()))  # 原数组
n = len(nums)
for i in range(n):  # 记录原顺序
    nums[i] = (nums[i], i)
nums.sort(key=lambda x: x[0])  # 排序
print(nums)
last = nums[0][0]
nums[0] = (1, nums[0][1])
for i in range(1, n):  # 离散化
    if nums[i][0] == last:
        last = nums[i][0]
        nums[i] = (nums[i - 1][0], nums[i][1])
    else:
        last = nums[i][0]
        nums[i] = (nums[i - 1][0] + 1, nums[i][1])
nums.sort(key=lambda x: x[1])  # 回到原顺序
print(nums)
nums = list(map(lambda x: x[0], nums))  # 原数组
print(nums)

方法二：将后出现的重复数字认为比先出现的同一数字大

nums = list(map(int, input().split()))  # 原数组
n = len(nums)
for i in range(n):  # 记录原顺序
    nums[i] = (nums[i], i)
nums.sort(key=lambda x: x[0])  # 排序
print(nums)
for i in range(n):  # 离散化
    nums[i] = (i, nums[i][1])
nums.sort(key=lambda x: x[1])  # 回到原顺序
print(nums)
nums = list(map(lambda x: x[0], nums))  # 原数组
print(nums)

离散化的应用

将坐标或数值范围离散化：当问题涉及到区间范围很大的整数（例如，1 到 10^9），直接处理这些数值会消耗大量内存和时间。通过离散化，可以将这些数值映射到一个较小的连续范围内，降低问题的复杂度。
减少不必要的数值范围：如果数组中包含大量重复的数值，离散化可以将重复的数值映射到相同的离散值，从而避免重复计算，减少不必要的存储开销。
在区间查询问题中使用离散化：一些问题中，可能会出现大量离散的区间，离散化通过压缩这些区间的数值范围，使得查询或更新操作更高效。