查找练习 hash——出现过的数字
*Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
有一个数据字典，里面存有n个数字(n<=100000)，小明现在接到一个任务，这项任务看起来非常简单——给定m个数字，分别查询这m个数字是否出现在字典之中；但是考虑到数据量的问题，小明找到了善于编程的你，希望你可以帮他解决这个问题。
输入
输入数据只有一组！
第一行包含两个整数n m，分别代表字典中数字的个数和要查询的数字的个数。
接着n行代表字典中的n个数字。
最后m表示要查询的数字。
输出
如果某个数字存在，则输出YES，否则输出NO*
示例输入
5 3
1
2
3
4
5
5
4
10
***/*
此方法慎用，除非明确数据的范围
*/
#include <bits/stdc++.h>
#define RR freopen("input.txt","r",stdin)
#define WW freopen("output.txt","w",stdout)
#define ClearAll(A,T) memset(A,T,sizeof(A))
using namespace std;
const int Max=110000;
const int Mod=110000;
bool Arr[Max];
int main()
{
int n,m,data;
ClearAll(Arr,false);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&data);
Arr[data]=true;
}
for(int i=1;i<=m;i++)
{
scanf("%d",&data);
if(Arr[data])
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
/**********************************************************************************************************************
#include <bits/stdc++.h>
#define RR freopen("input.txt","r",stdin)
#define WW freopen("output.txt","w",stdout)
#define ClearAll(A,T) memset(A,T,sizeof(A))
using namespace std;
const int Max=110000;
const int Mod=110000;
struct Num
{
int num;
Num *next;
}Arr[Max];
int main()
{
int n,m,data,a;
Num *p;
for(int i=0;i<Max;i++)
{
Arr[i].next=NULL;
}
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&data);
a=data%Mod;
p=new Num;
p->num=data;
p->next=Arr[a].next;
Arr[a].next=p;
}
for(int i=1;i<=m;i++)
{
scanf("%d",&data);
a=data%Mod;
p=Arr[a].next;
while(p)
{
if(p->num==data)
{
break;
}
p=p->next;
}
if(p)
{
printf("YES\n");
}
else***重点内容***
{
printf("NO\n");
}
}
return 0;
}***
版权声明：本文为博主原创文章，未经博主允许不得转载。