NOIP不让用的数据结构坚决不用!
$$\ce{CO2+C ->[\Delta] 2CO}$$

但不影响去实现它。

什么是unordered_map

增删改查的时间复杂度是 O(1)
insert()
erase()
find()
clear()
实现方式是`hash`

最后一句话是重点,所以hash要走起了。
仔细分析,增删改查都可以通过数组来完成。包括清空可以用clear

结构体实现存储

struct mmap{
    int hash[N];
    int w[N];
    int INF;
}

初始化clear

初始化,通过memset实现,传入参数为0x3f之类的

    void clear(int a){
        memset(hash,a,sizeof hash);
        memset(w,a,sizeof hash)
        INF=hash[0];
    }

查找find

查找操作,查找元素的下标。

    int findh(int a){
        int a=(k%N+N)%N;
        while(hash[k]!=INF&&hash[k]!=a){
            k++;
            if(k==N)k=0;
        }
        return k;
    }
    int find(int a){
        int t = lower_bound(w,w+n,a);
        if(w[t]==a)return hash[t];
        else return -1;
    }  

修增change

    void inserte(int a,int b){
        w[findh(a)]=b;
    }

删除delt

    void delt(int a){
        w[findh(a)]=INF;
        hash[findh(a)]=INF;
    }

汇总

struct mmap{
    int hash[N];
    int w[N];
    int INF;
    void clear(int a){
        memset(hash,a,sizeof hash);
        memset(w,a,sizeof hash)
        INF=hash[0];
    }
    int findh(int a){
        int a=(k%N+N)%N;
        while(hash[k]!=INF&&hash[k]!=a){
            k++;
            if(k==N)k=0;
        }
        return k;
    }
    int find(int a){
        int t = lower_bound(w,w+n,a);
        if(w[t]==a)return hash[t];
        else return -1;
    }
    void inserte(int a,int b){
        w[findh(a)]=b;
    }
    void delt(int a){
        w[findh(a)]=INF;
        hash[findh(a)]=INF;
    }
}
name.com购买域名廉价稳定无需备案 年付.xyz.site.life$3点击购买赠送5$优惠券
racknerd购买无需备案CN2服务器,速度高速稳定节日优惠力度强 节日会推出各种优惠套餐【点击注册】目前推出3H2.5G40GB6T每年$27.80两年$55.60套餐【快来注册
Last modification:May 20th, 2020 at 07:46 am
觉得好的话就评论,转发,投币。