离散化

说明

num[]表示离散化之前的数组,下标从1~n

a[]表示离散化之后的数组,下标从1~n

lsh[]表示离散化的缓存数组,下标为1~cnt

函数返回值为cnt

使用方法

  1. 输入n
  2. for(i: 1->n) scanf(num[i]);
  3. ll cnt = discrete()

Tips

  • 考虑内存问题,会爆内存的话换int
  • 需要加algorithmcstring头文件

模版

版本一

说明: 此方法为完整的离散化,表示不考虑重复数字num[i]为第a[i]大的数

num数组: 1 5 5 5 100

a数组: 1 2 2 2 3

ll num[maxn],lsh[maxn],a[maxn],n;
ll discrete(){
    memcpy(lsh, num, sizeof(lsh));
    stable_sort(lsh+1, lsh+1+n);
    ll cnt=unique(lsh+1, lsh+1+n)-lsh-1;
    for (ll i=1; i<=n; i++)
        a[i]=lower_bound(lsh+1, lsh+cnt+1, num[i])-lsh;
    return cnt;
}

版本二

说明: 此方法为特殊的离散化,表示考虑重复数字num[i]为第a[i]大的数

num数组: 1 100 5 5 5

a数组: 1 5 2 2 2

ll num[maxn],lsh[maxn],a[maxn],n;
ll discrete(){
    memcpy(lsh, num, sizeof(lsh));
    stable_sort(lsh+1, lsh+1+n);
    ll cnt=n;
    for (ll i=1; i<=n; i++)
        a[i]=lower_bound(lsh+1, lsh+cnt+1, num[i])-lsh;
    return cnt;
}

results matching ""

    No results matching ""