PAT甲级1078 hashing

深碍√TFBOYSˉ_ 2023-07-24 13:13 17阅读 0赞

题目大意：  
利用除留余数法建hashtable，然后利用平方探查法缓解hash值冲突问题，然后要你输出每个输入的值在hashtable中的下标位置，如果不存在的话输出 -  
**解题思路：**  
1.当给的表长msize不为素数时，需要先求出比msize大的最小的素数  
2.如果temp%msize的位置已经有元素，那么对H(key)+k\*k位置进行查找，如果H(key)+k \*k大于msize，则取模msize。若没找到合适的位置则递增k，当k在【0，msize）范围内都没有找到一个合适的位置的话，那么temp无法插入hashtable，输出-  
**注意：**  
大于10000的最小素数为止，所以在利用素数筛选法的时候尽量把数组开大一点  
**代码：**

#include<cstdio>
    #include<vector>
    using namespace std;
    int main()
    { 
        int msize,n;
        scanf("%d%d",&msize,&n);
        int isprime[10099];//1表示是素数,不够的话增加范围，适用最后一个测试案例
        for(int i=0;i<10099;i++)isprime[i]=1;
        isprime[1]=0;
        for(int i=2;i<6000;i++)//素数筛查法
        { 
            if(isprime[i]==1)
            { 
                for(int j=i*2;j<10099;j+=i)isprime[j]=0;
            }
        }
        while(isprime[msize]!=1)msize++;
        vector<int> v(msize,-1),output(n);
        for(int i=0;i<n;i++)
        { 
            int temp,k=0;
            bool flag=false;
            scanf("%d",&temp);
            while(k<msize)
            { 
                int index=temp+k*k;
                if(index>=msize)index=index%msize;//判定条件很关键
                if(v[index]==-1)//未被占用
                { 
                    output[i]=index;
                    v[index]=temp;
                    flag=true;
                    break;
                }
                else k++;
            }
            if(!flag)output[i]=-1;
        }
        printf("%d",output[0]);
        for(int i=1;i<n;i++)
        { 
            if(output[i]!=-1)printf(" %d",output[i]);
            else printf(" -");
        }
        return 0;
    }