codevs 1230_元素查找_hash

发布于 2019-05-04  9 次阅读


题目描述

给出n个正整数,然后有m个询问,每个询问一个整数,询问该整数是否在n个正整数中出现过。


思路

水hash,复习一下。。。
O(n)


#include 
#define M 100007
int a[M+1];
int insert(int x)
{
    int i=x;
    while (a[i]!=0&&a[i]!=x) i++;
    a[i]=x;
}
int find(int x)
{
    int i=x;
    while (a[i]!=x&&a[i]!=0) i++;
    if (a[i]==x) return 1;
    else return 0;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        insert(x);
    }
    for (int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        if (find(x))
            printf("YES\n");
        else printf("NO\n");
    }
}
]]>