离散化

发表于 更新于 分类于 Valine： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

有时我们希望使用一些对数据大小或类型有限制的数据结构，例如树状数组（要求整型并且因为内存的关系最大数据范围通常为1e6量级）。

但是如果我们的数据个数在1e6之内，并且我们只关心数据的序，我们就可以在非负整数和我们的数据集之间建立映射来使用树状数组（或其他有限制的数据结构）。

那么这里我们就期望一个帮助建立映射的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

// 返回一个整型数组包含 [0, arr.size()) 的数字，且和arr具有一致的序
template<typename T, typename CMP=less<T>>
vector<int> get_rank(const vector<T>& arr, CMP cmp=CMP()){
    vector<int> idx(arr.size());
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](auto i, auto j){
        return cmp(arr[i], arr[j]);
    });
    // 我们在不改变arr的情况下对其下标数组进行排序
    // 排序好后，对于任意i < j有arr[idx[i]] <= arr[idx[j]] (1)
    // 如果我们构造一个rank，令rank[idx[i]] = i, 0<=i<n，
    // 那么显然对于任意i < j有rank[idx[i]]=i < j=rank[idx[j]]
    // 可以看到如果忽略(1)式中的等号，rank就已经和arr具有一致的序
    // 所以下面我们就按这个思路，再顺便处理一下并列的情况就行了
    vector<int> rank(arr.size());
    rank[idx[0]] = 0;
    for(int i=1; i<arr.size(); i++){
        if(arr[idx[i]] == arr[idx[i-1]]){
            rank[idx[i]] = rank[idx[i-1]];
        } else {
            rank[idx[i]] = i;
        }
    }
    return rank;
}

上面的得到rank实际上是 arr -> 同序非负整数集 的映射。