离散化

摘要: 离散化的原理和代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

离散化属于排序算法的应用，目的是把无穷大集合中的若干元素映射为有限集合，以便于统计。

很多时候，问题的范围是定义在整数集合 $\mathbb{Z}$ 上，但是只涉及其中 m 个值，并且与数值的绝对大小无关，此时就可以将着 m 个数与 1~m 建立映射关系。如果有某个算法的时间/空间复杂度为 $O(|\mathbb{Z}|)$，离散化后，时间/空间复杂度变为 $O(m)$。

一维离散化

算法原理

离散化的核心思想是将分布大却数量少(稀疏)的数据进行集中化的处理，减少空间复杂度。

具体就是用排名数组代替原数组，流程大致是排序、去重、取原始数据的排名。

比如原始数组为 nums，排序去重后的数组为 x。则对原始数组中的数据 nums[i]，它的从 0 开始计的排名是：

upper_bound(x.begin(), x.end(), nums[i]) - x.begin();

例如考虑 nums = [-7, 0, 4, 1e3+7, 1e7+7, 4, -1e5] 的离散化过程。离散化之后，大大缩小了数据(这里的权值)范围，并且可以用作数组下标。

在处理数轴上的元素的统计问题时，经常用线段树处理。如果元素在数轴上的可能的位置非常大，而元素数量不太大，此时可以先把所有元素离散化，每个元素对应一个排名，称其为权值，然后再用线段树维护这些权值，即可完成原始的统计需求。参考 离散化,权值线段树,权值树状数组。

代码模板 (C++)

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int find(int v, const vector<int>& aa) // 从 nums 的值找到对应的离散化之后的值
{
    return lower_bound(aa.begin(), aa.end(), v) - aa.begin() + 1;
}

vector<int> discretization(const vector<int>& a)
{
    int n = a.size();
    vector<int> aa = a;
    sort(aa.begin(), aa.end());
    aa.erase(unique(aa.begin(), aa.end()), aa.end());
    return aa;
}

测试

int main()
{
    vector<int> a({-7, 0, 4, (int)1e6 + 7, 9, 4, (int)-1e3 + 7});
    for(int x: a)
        cout << x << " ";
    cout << endl;
    vector<int> aa = discretization(a);
    for(int x: aa)
        cout << x << " ";
    cout << endl;

    int n = a.size();
    vector<int> result(n);
    for(int i = 0; i < n; ++i)
    {
        int idx = find(a[i], aa);
        cout << idx << " ";
        // cout << aa[idx] << " ";
    }
    cout << endl;
}

结果如下：

-7 0 4 1000007 9 4 -993
-993 -7 0 4 9 1000007
2 3 4 6 5 4 1

题目

• 1331. 数组序号转换

给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。

序号代表了一个元素有多大。序号编号的规则如下：

• 序号从 1 开始编号。
• 一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
• 每个数字的序号都应该尽可能地小。

示例 1：
输入：arr = [40,10,20,30]
输出：[4,1,2,3]
解释：40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。

示例 2：
输入：arr = [100,100,100]
输出：[1,1,1]
解释：所有元素有相同的序号。

示例 3：
输入：arr = [37,12,28,9,100,56,80,5,12]
输出：[5,3,4,2,8,6,7,1,3]

提示：

0 <= arr.length <= 1e5
-1e9 <= arr[i] <= 1e9

代码 (C++)

int find(int v, const vector<int>& aa) // 从 nums 的值找到对应的离散化之后的值
{
    return lower_bound(aa.begin(), aa.end(), v) - aa.begin() + 1;
}

vector<int> discretization(const vector<int>& a)
{
    int n = a.size();
    vector<int> aa = a;
    sort(aa.begin(), aa.end());
    aa.erase(unique(aa.begin(), aa.end()), aa.end());
    vector<int> result((int)a.size());
    for(int i = 0; i < n; ++i)
        result[i] = find(a[i], aa);
    return result;
}


class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        return discretization(arr);
    }
};

---

二维离散化

离散化的核心思想是将数据分布范围大但数量少(稀疏)的数据进行集中化的处理，减少空间复杂度。

算法原理

首先回顾一维离散化。一维离散化的主要应用之一是在用权值树状数组或者权值线段树做区间内的统计时，数组下标是权值，数组的值是权值的计数。因为权值的范围可能会很大且有可能有负数和小数，例如 $[-1e9, 1e9]$，开不出这么大的数组。而统计过程只关心元素大小关系，不关心元素的具体的值，并且这么大的数据范围里有出现过的权(最终计数 $>1$ 的权)很少，因此可以使用离散化的方法把出现过的权按照大小关系映射到 $[0,1,2,\cdots]$，这样既保持了元素的大小关系，又可以把权当做数组下标使用了。

例如考虑一个 16*16 的网格上的寻路问题。有5个障碍点(6, 0), (11, 4), (5, 8), (3, 9), (10, 14)。对结果有影响的行如下(未去重)：

1. 起点终点所在行 i = {0, 15}；
2. 障碍点所在行 i = {3, 5, 6, 10, 11}；
3. 障碍点所在行的相邻) i = {2, 4, 4, 6, 5, 7, 9, 11, 10,12}

对结果有影响的列如下(未去重)：

1. 起点终点所在列 j = {0, 15}
2. 障碍点所在列 j = {0, 4, 8, 9, 14}
3. 障碍点所在列的响铃列 j = {1, 3, 5, 7, 9, 8, 10, 13, 15}

分别对这些对结果有影响的行和列做离散化，得到一个较小 12 * 12 的网格。

二维离散化之后，原来的起点和终点(0,0), (15, 15) 变成了(0, 0), (12, 12)；原有的5个障碍点也有相应的变化：

(6,0) -> (5,0)
(11,4) -> (9,3)
(5,8) -> (4,6)
(3,9) -> (2,7)
(10,14) -> (9,11)

新网格的规模缩小，可以开的出网格规模的数组了，起点，终点，障碍点，障碍点的相邻点的位置关系保持不变。在新网格上对起点和终点的寻路问题可做。

基于前面的描述，二位离散化的算法如下：

1. 开两个空的vector，x 和 y，分别记录对结果有影响的横坐标，纵坐标
2. 开两个哈希表 setx, set_y, 分别记录已经压进 x, y 的值
3. 枚举所有障碍点、起点、终点 (i, j)
    1) 枚举 i - 1(若 i > 0), i, i + 1(若 i < n - 1) , 若未在 set_y 中(未压进x过)，则压进 x 并插入 set_x
    2) 枚举 j - 1(若 j > 0), j, j + 1(若 i < m - 1) , 若未在 set_y 中(未压进y过)，则压进 y 并插入 set_y
4. 对 x, y 分别做一维离散化的排序，去重
5. 开出离散化后的网格 vector<vector<int> > new_grid
6. 确定网格 new_grid 中的起点，终点坐标
7. 离散化后的障碍点记录到 new_grid

代码模板 (C++)

void discretization(const vector<vector<int> >& a, vector<int>& x, vector<int>& y)
{
    unordered_set<int> set_x, set_y;
    for(const vector<int> aa: a)
    {
        int i = aa[0], j = aa[1];
        for(int k = i - 1; k <= i + 1; ++k)
        {
            if(set_x.find(k) == set_x.end())
            {
                x.push_back(k);
                set_x.insert(k);
            }
        }
        for(int k = j - 1; k <= j + 1; ++k)
        {
            if(set_y.find(k) == set_y.end())
            {
                y.push_back(k);
                set_y.insert(k);
            }
        }
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    y.erase(unique(y.begin(), y.end()), y.end());
}

int _find(int v, const vector<int>& x)
{
    return lower_bound(x.begin(), x.end(), v) - x.begin();
}

题目

力扣上有一道题目可以用二位离散化来处理范围非常大的二维数据。参考文章 【搜索难题】力扣1036-有限BFS,二维离散化。

---