「LeetCode」数据预处理 - 离散化

2020-05-08
摘要: 本文介绍了非常常用的技巧:数据预处理 - 离散化。

数据离散化#

当问题只受到数据的相对大小关系影响时,我们可以用排名代替原数据。离散化本质上是一种哈希,它保持原序列相对大小关系,并将其映射成正整数。当原数据很大却很稀疏时,为整个数据范围开辟数据耗费过多空间;或者含有负数小数时,难以将其表示为数组下标。此时一些算法和数据结构无法运行(比如树状数组 BIT),我们可以考虑将数据离散化。

实现#

基本思路就是将原序列排序去重,利用 STL 的排序和去重函数即可。再在得到的新序列中做一个二分查找,把原序列映射至新的下标。由于各种操作的复杂度都是 $N(\log(N))$,所以离散化的复杂度就是 $N(\log(N))$。如果需要从大到小映射,只需要在 sortlower_bound 中增加 greater<int>() 即可,见示例代码中的注释部分。

vector 示例代码#

vector<int> A{10, 23, 35, 3, -40, 3};
vector<int> B(A.begin(), A.end());
vector<int> C(A.size(), 0);

// 先排序,再去重
sort(B.begin(), B.end()); // [-40, 3, 3, 10, 23, 35]
// sort(B.begin(), B.end(), greater<int>()); // [35, 23, 10, 3, 3, -40]
unique(B.begin(), B.end()); // [-40, 3, 10, 23, 35]

for(int i = 0; i < A.size(); ++i) {
    // 映射到 1...N
    C[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin() + 1; // [3, 4, 5, 2, 1, 2]
    // C[i] = lower_bound(B.begin(), B.end(), A[i], greater<int>()) - B.begin() + 1; // [3, 2, 1, 4, 5, 4]
}