离散化的一种姿势

之前我的离散化方法一直用set和map做，感觉使用stl不够优越。刚刚发现线段树PPT给了一种离散化的新姿势。。。

ax数组：要进行离散化的数组

bx数组：离散化后的数组

id数组：ax数组的rank数组。即排序后id[i]表示为ax数组中第i大的数的位置。

如果要从原数->离散化后的数，还是需要用map，但是bx数组已经与ax数组形成了对应关系，所以map完全可以避免。

#include<bits/stdc++.h>
#define eps 1e-9
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define MAXN 1005
#define MAXM 40005
#define INF 0x3fffffff
#define PB push_back
#define MP make_pair
#define X first
#define Y second
#define lc (k<<1)
#define rc ((k<<1)1)
using namespace std;
typedef long long LL;
int i,j,k,n,m,x,y,T,ans,big,cas,num,len;
bool flag;

int ax[MAXN],bx[MAXN],mp[MAXN],id[MAXN];
bool cmp(const int &x,const int &y)
{
    return ax[x]<ax[y];
}

void discreatize(int n)
{
    for (int i=0;i<n;i++) id[i]=i;
    sort(id,id+n,cmp);//排序后id[i]表示为ax数组中第i大的数的位置。 
    mp[1]=ax[id[0]];//对应关系 
    bx[id[0]]=1;//bx数组为ax离散化后的数组。 
    for (int i=1,k=1;i<n;i++)
    {
        if (ax[id[i]]==ax[id[i-1]]) bx[id[i]]=k;
        else mp[++k]=ax[id[i]],bx[id[i]]=k;
    }
}
int main()
{
    scanf("%d",&n);
    for (i=0;i<n;i++) scanf("%d",&ax[i]);
    discreatize(n);
    printf("id:\n");
    for (i=0;i<n;i++) printf("%d ",id[i]);
    printf("\nbx:\n");
    for (i=0;i<n;i++) printf("%d ",bx[i]);
    printf("\n");
    return 0;
}

离散化的一种姿势

推荐阅读