关于hash

P2249 【深基13.例1】查找

PengDave @ 2024-01-23 10:53:32

空闲时我试着再用手打 hash 解决这题,AC是AC了,却发现还没lower_bound快, O(1) 还没O(\log{n}) 快?这是咋回事呢?

#include<bits/stdc++.h>
using namespace std;
// long long a[1000010];
const int mod=1000007;
struct pdy_hash{
    struct data{
        long long ind;
        int value;
    };
    vector<data> pt[mod+5];
    int pmod(int n){
        return (n%mod+n)%mod;
    }
    int &operator[](long long x){
        long long tmp=pmod(x);
        for(int i=0;i<pt[tmp].size();i++){
            if(pt[tmp][i].ind==x){
                return pt[tmp][i].value;
            }
        }
        pt[tmp].push_back(data{x,0});
        return (pt[tmp].end()-1)->value;
    }
//  pdy_hash(){
//      for(int i=0;i<mod;i++){
//          pt[i].resize(0);
//      }
//  }
};
pdy_hash a;
int main(){
    long long n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        long long tmp;
        scanf("%lld",&tmp);
        if(!a[tmp]){
            a[tmp]=i;
        }
    }
    for(int i=0;i<m;i++){
        long long q,ans=-1;
        scanf("%lld",&q);
        // if(binary_search(a+1,a+n+1,q)){
        //     ans=lower_bound(a+1,a+n+1,q)-a;
        // }
        int tmp=a[q];
        if(tmp){
            ans=tmp;
        }
        printf("%lld ",ans);
    }
    return 0;
}

by call_of_silence @ 2024-01-23 11:09:24

@PengDave

以后请把hash看成\log n,常数太大


by Y_QWQ_Y @ 2024-01-23 11:13:27

@PengDave hash 大佬膜拜!我太菜了直接 map


by PengDave @ 2024-01-23 20:11:52

@call_of_silence thanks,知道了


|