离散化

离散化本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的顺序关系。

通俗地讲，就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。

通俗地讲，就是把无穷大集合中的若干个元素映射为有限集合以便于统计。

离散化数组

我们可以把a数组排序并去掉重复的数值，得到有序数组b[1]~b[m]，
在b数组的下标i与数值b[i]之间建立映射关系。
若要查询整数i(1<=i<=m)代替的数值，只需直接返回b[i]
若要查询整数a[j](1<=j<=n)被哪个1~m之间的整数代替，只需在数组b中二分查找a[j]的位置即可

void discreate(){
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        if (i == 1 || a[i] != a[i - 1])
            b[++m] = a[i];
}
int query(int x){
    return lower_bound(b + 1, b + m + 1, x) - b;
}

#include <bits/stdc++.h>
using namespace std;
int a[110], b[110], n, m;
vector<int> A;
void discreate(){
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        if (i == 1 || a[i] != a[i - 1])
            b[++m] = a[i];
}
int query(int x){
    return lower_bound(b + 1, b + m + 1, x) - b;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    discreate();
    for (int i = 1; i <= n; i++) cout << query(a[i]) << ' ';
    puts("");
    return 0;
}

离散化vector

同样地，我们也可以对 vector 进行离散化：

// a[i]是原数组，b[i]存储离散化新的编号
#include <bits/stdc++.h>
using namespace std;
int a[110], b[110], n;
vector<int> A;
int main(){
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        A.push_back(a[i]);
    }
    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end());
    for (int i = 0; i < n; i++)
        b[i] = lower_bound(A.begin(), A.end(), a[i]) - A.begin();
    for (int i = 0; i < n; i++) cout << b[i] << ' ';
    puts("");
    return 0;
}