最近做了不少离散化的题，被折磨的死去活来，所以决定还是写一下离散化的操作。

离散化操作简介：当数据范围很大，但是数据数量很小，或者数据为浮点型时，此时便需要离散化。

首先第一种方法：

这是y总最喜欢的也是我第一个学会，并且很常用的离散化方法。(使用vector去重进行离散化)

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

vector<int> q;

/*int find(int x)//find函数二选一即可，第一种为手写二分，第二种则使用lower_bound函数。
{
    int l=0,r=q.size()-1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(q[mid]>=x) r=mid;
        else l=mid+1;
    }
    return l;
}*/

int find(int x)
{
    return lower_bound(q.begin(),q.end(),x)-q.begin();
}

int main()
{
    int n;//输入数据数量
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int a;
        cin>>a;
        q.push_back(a);
    }

    sort(q.begin(),q.end());//对数据进行排序
    q.erase(unique(q.begin(),q.end()),q.end());//对数据去重

    int query;//输入要查询的数据
    cin>>query;
    cout<<find(query);
}

输入

3
99999 111 2
2

输出

0

通过上述实例，可以看出，离散化以后数组被压缩为三个整数，查询则会返回排序后下标。

第二种方法：

使用unordered_map进行离散化操作。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

unordered_map<int,int> q;
int cnt;

int make(int x)
{
    if (q.count(x)) return q[x];//如果之前存过这个数，直接返回val
    return q[x] = cnt ++ ;//不存在则将这个数作为key，cnt为val，存储成键值对
}

int main()
{
    int x, y, e;
    cin>>x>>y;
    x=make(x);
    y=make(y);
    cout<<x<<" "<<y;
}

输入

99999 1000

输出

0 1

此方法也能进行离散化，离散化前的数值作为key，离散后的下标作为val存储在map中，查询效率平均为O(1);

相对以上两种方法，其实各有利弊，按个人喜好或题目要求选择即可。