哈希查找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;
}

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