离散化

luckydrawbox · 2021-08-28 23:07:40 · 算法·理论

把长度为 n 的 a 数组映射成只有 1\sim tot 的整数的 b 数组，其中返回值 tot 是 a 中元素个数。

int discrete(int n,int *a){
    int b[N];
    for(int i=1;i<=n;i++)
        b[i]=a[i];
    sort(b+1,b+n+1);
    int tot=unique(b+1,b+n+1)-(b+1);
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    return tot;
}

空间复杂度 O(n)，时间复杂度 O(n\log n)。

back