离散化

_Cheems · 2023-03-13 13:53:34 · 个人记录

作用

使不连续的数用一段连续空间存储。

通常搭配其它算法使用。

补充知识

• lower_bound( 起始地址 ， 结束地址 ， 查找值 ) ：

  用于在指定区域内查找不小于目标值的第一个元素，也就是大于等于。

• unique( 起始地址 ， 结束地址 ) ：

  将给定区间的元素去重。注意不是真正的去重，只是把相邻的相同元素去掉，因此要搭配排序使用。

• binary_search( 起始地址 ，结束地址 ，要查找的数值 ) ：

  返回是否存在这么一个数，是 bool 值。

实现思路

法一：辅助数组

开一个辅助数组来确定大小。

直接上程序，很好理解。

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],b[1000005],rank[1000005];
//a[]：原数组，b[]：离散化数组，rank[]：辅助数组 
int main()
{
    cin>>n;
    for(int i=1; i<=n;i++)
    {
        scanf("%lld",&a[i]);
        rank[i]=a[i];
    }
    sort(rank+1,rank+1+n);
    int len=unique(rank+1,rank+1+n)-(rank+1); 
    //len 是长度，所以要减去 rank+1
    for(int i=1; i<=n;i++)
    {
        b[i]=lower_bound(rank+1,rank+1+len,a[i])-rank; 
        //lower_bound 是第一个大于等于的数
        //这里的下标是 1 开始的 
        //b[i]存下标，所以减去的是 rank
    } 
    for(int i=1; i<=n;i++) cout<<b[i]<<' ';
    return 0;
}

法二：结构体

不是很常用，只要知道就好。

结构体存储原数组的值和下标。

然后以值的大小排序，用二分确定在原数组中的相对大小。