进阶数据结构——离散化

创作时间:

作者:

@小白创作中心

进阶数据结构——离散化

引用

CSDN

https://blog.csdn.net/ycs66/article/details/145595750

离散化是一种将连续数据映射到有限离散值的技术，通常用于处理大规模数据或稀疏数据。通过将原始数据重新编号或映射，可以减少数据的规模和复杂度，同时保留数据的相对关系。

离散化的应用场景

区间查询与更新：在线段树或树状数组中，离散化可以将大范围的坐标映射到小范围的索引，节省空间和时间。例如LeetCode 315. 计算右侧小于当前元素的个数。
统计与计数：在统计频次或计数问题中，离散化可以减少数据规模，提高效率。例如LeetCode 493. 翻转对。
图论与网络流：在图论问题中，离散化可以将大范围的节点编号映射到小范围，简化问题。例如LeetCode 685. 冗余连接 II。
几何问题：在几何问题中，离散化可以将连续的坐标映射到离散的网格点，简化计算。例如LeetCode 850. 矩形面积 II。

离散化的实现步骤

数据收集：收集所有需要离散化的数据点（如坐标、值等）。
排序与去重：对数据点进行排序，并去除重复值。
映射与编号：将原始数据点映射到离散的索引（通常从 0 或 1 开始）。
应用离散化：使用映射后的索引代替原始数据点进行计算或存储。

离散化的复杂度分析

时间复杂度：
排序与去重：O(nlogn)，其中 n 是数据点的数量。
映射与编号：O(n)。
空间复杂度：
存储映射关系：O(n)。

离散化的优化技巧

二分查找优化：在映射过程中，使用二分查找快速确定数据点的离散索引。
动态离散化：在动态数据流中，实时维护离散化映射。
多维度离散化：在多维数据中，分别对每个维度进行离散化。

常见误区与调试技巧

误区一：离散化会丢失信息

澄清：离散化仅改变数据的表示方式，不改变数据的相对关系。

误区二：离散化适用于所有问题

澄清：离散化适用于数据范围大但数据点稀疏的问题，对于密集数据可能不适用。

调试方法

打印映射关系：在离散化后输出映射关系，检查是否正确。
可视化数据分布：绘制原始数据和离散化后的数据分布，检查一致性。

代码模版（C++）

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

template<class T>
class Dicretizer {
private:
    vector<T>m_data;
public:
    void addData(T v);
    void process();
    int getData(T v) const;
    int size()const;
};

template<class T>
void Dicretizer<T>::addData(T v) {
    m_data.push_back(v);
}

template<class T>
void Dicretizer<T>::process() {
    sort(m_data.begin(), m_data.end());
    int lastId = 0;
    for (int i = 1; i < m_data.size(); i++) {
        T t = m_data[i];
        if (t != m_data[lastId]) {
            m_data[++lastId] = t;
        }
    }
    while (lastId < m_data.size() - 1) {
        m_data.pop_back();
    }
}

template<class T>
int Dicretizer<T>::getData(T v) const {
    int l = -1, r = m_data.size();
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (m_data[mid] >= v)r = mid;
        else l = mid;
    }
    if (m_data[r] != v || r == m_data.size())return -1;
    return r;
}

template<class T>
int Dicretizer<T>::size() const {
    return m_data.size();
}

int main() {

    return 0;
}

经典例题

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

template<class T>
class Dicretizer {
private:
    vector<T>m_data;
public:
    void addData(T v);
    void process();
    int get(T v) const;
    int size() const;
};

template<class T>
void Dicretizer<T>::addData(T v) {
    m_data.push_back(v);
}

template<class T>
void Dicretizer<T>::process() {
    sort(m_data.begin(), m_data.end());
    int lastId = 0;
    for (int i = 1; i < m_data.size(); i++) {
        T x = m_data[i];
        if (x != m_data[lastId]) {
            m_data[++lastId] = x;
        }
    }
    while (lastId < m_data.size() - 1) {
        m_data.pop_back();
    }
}

template<class T>
int Dicretizer<T>::get(T v) const {
    int l = -1, r = m_data.size();
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (m_data[mid] >= v)r = mid;
        else l = mid;
    }
    if (r == m_data.size() || m_data[r] != v)return -1;
    return r;
}

template<class T>
int Dicretizer<T>::size() const {
    return m_data.size();
}

int a[100001];

int main() {
    int n;
    cin >> n;
    while (n--) {
        int s;
        cin >> s;
        Dicretizer<int> d;
        for (int i = 0; i < s; i++) {
            int x;
            cin >> x;
            a[i] = x;
            d.addData(x);
        }
        d.process();
        for (int i = 0; i < s; i++) {
            cout << d.get(a[i]) + 1 << ' ';		//因为数组下标是从0开始,所以加一
        }
        cout << endl;
    }
    return 0;
}

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

template<class T>
class Dicretizer {
private:
    vector<T>m_data;
public:
    void addData(T v);
    void process();
    int getData(T v) const;
    int size()const;
};

template<class T>
void Dicretizer<T>::addData(T v) {
    m_data.push_back(v);
}

template<class T>
void Dicretizer<T>::process() {
    sort(m_data.begin(), m_data.end());
    int lastId = 0;
    for (int i = 1; i < m_data.size(); i++) {
        T t = m_data[i];
        if (t != m_data[lastId]) {
            m_data[++lastId] = t;
        }
    }
    while (lastId < m_data.size() - 1) {
        m_data.pop_back();
    }
}

template<class T>
int Dicretizer<T>::getData(T v) const {
    int l = -1, r = m_data.size();
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (m_data[mid] >= v)r = mid;
        else l = mid;
    }
    if (m_data[r] != v || r == m_data.size())return -1;
    return r;
}

template<class T>
int Dicretizer<T>::size() const {
    return m_data.size();
}

#define maxn 200001

struct HB {
    int h, b;
}hb[maxn];
int k[maxn], maxv[maxn];		//k作为询问数组，maxv代表限高的最大美丽值

bool cmp(const HB& a, const HB& b) {
    return a.h < b.h;
}

int main() {
    Dicretizer<int>d;
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> hb[i].h;
        d.addData(hb[i].h);
    }
    for (int i = 0; i < n; i++) {
        cin >> hb[i].b;
    }
    for (int i = 0; i < q; i++) {
        cin >> k[i];
        d.addData(k[i]);
    }
    d.process();
    for (int i = 0; i < n; i++) {
        hb[i].h = d.getData(hb[i].h);
    }
    for (int i = 0; i < q; i++) {
        k[i] = d.getData(k[i]);
    }
    sort(hb, hb + n, cmp);
    maxv[d.size()] = -1;
    int j = n - 1;
    for (int i = d.size() - 1; i >= 0; i--) {
        maxv[i] = maxv[i + 1];
        while(j >= 0 && hb[j].h == i) {
            if(hb[j].b > maxv[i]) {
                maxv[i] = hb[j].b;
            }
            j--;
        }
    }
    for (int i = 0; i < q; i++) {
        int x = k[i];
        cout << maxv[x] << endl;
    }
    return 0;
}