哈希查找1

哈希查找1

时间： 1ms        内存：128M

描述：

 题目描述
有一个数据字典，里面存有n个不同数字(n<=100000)，以哈希函数为f(x)=x+1存在数据字典中。小明现在接到一个任务，这项任务看起来非常简单——给定m个数字，分别查询这m个数字是否出现在字典之中；但是考虑到你是个优秀的程序员，如果查询的数存在表中你不仅要告诉小明数据存在还得贴心的告诉小明他查询的数的在数据字典中的下标（下标从2开始到n+1）。若查询的数不存在，则返回-1；

输入：

第一行包含两个整数n m，分别代表字典中数字的个数和要查询的数字的个数。
接着n个数代表字典中存在的n个数字。（1<=a[i]<=100000）
最后m行表示要查询的数字

输出：

输出m行
如果某个数字存在，则输出下标，否则输出-1

示例输入：

9 3
1 2 3 4 5 6 7 8 9
3
7
0

示例输出：

4
8
-1

提示：

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

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n,m,i,x,t;
    int a[100001]={0};
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
    {
        scanf("%d",&x);
        a[x+1]=1;
    }
    while(m--)
    {
        scanf("%d",&t);
        if(a[t+1]==1)
            printf("%d",t+1);
        else
            printf("-1");
        printf("\n");
    }
    return 0;
}

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

#include<stdio.h>
#define N 100000
void intsert(int a[],int n,int key)
{
    int i;
    i=key;
    a[i+1]=key;
}
int search(int a[],int n,int k)
{
    int i;
    i=k+1;
    if(a[i]==0)
    {
        i=-1;
    }
    return i;
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int a[N]={0};
    int i,key;
    for(i=1;i<n+1;i++)
    {
        scanf("%d",&key);
        intsert(a,n,key);
    }
    int t=m,k;
    while(t>0)
    {
        t--;
        scanf("%d",&k);
        int ww=search(a,n,k);
        printf("%d\n",ww);
    }
    return 0;
}

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