哈希查找2

哈希查找2

时间： 1ms        内存：128M

描述：

根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)=Key%p,将关键字映射到长度为p的哈希表中，用线性探测法解决冲突。重复关键字放在hash表中的同一位置。

输入：

输入数据第一行为两个正整数N(N <= 1000)和p(p 为大于等于 N的最小素数)，N是关键字总数，p是hash表长度，第2行给出N个正整数关键字，数字间以空格间隔。

输出：

输出每个关键字在hash表中的位置，以空格间隔。注意最后一个数字后面不要有空格。

示例输入：

5 5
24 39 61 15 39

示例输出：

4 0 1 2 0

提示：

参考答案（内存最优[1120]）：

#include <stdio.h>


int main()
{
   int a,b,c,d,e,i;
   scanf("%d %d",&a,&b);
   int n[b],m[a],o[a];
   for(c=0;c<=b;c++)
    n[c]=0;
   for(c=0;c<a;c++)
   {scanf("%d",&o[c]); e=0;
   for(d=0;d<c;d++)
   {
       if(o[c]==o[d])
       {printf("%d ",m[d]);
       e=1;
       break;}
   }
   if(e==0)
   {i=o[c]%b;
   while(n[i]!=0)
   {
       i++;
       i%=b;
   }
   n[i]=o[c];
   m[c]=i;
   printf("%d ",i);}
   }
    return 0;
}

参考答案（时间最优[1]）：

#include<stdio.h>

int main()
{
    int n,p,i,j,k=0;
    int a[1000],b[1000],c[1000];
    scanf("%d %d",&n,&p);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n;i++)
    {
        j=a[i]%p;
        while(b[j]!=0)
        {
            if(b[j]==a[i])
            break;
            j++;
            j%=p;
        }
        b[j]=a[i];
        c[k]=j;
        k++;
    }
    for(i=0;i<k-1;i++)
        printf("%d ",c[i]);
    printf("%d\n",c[k-1]);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。