首页 > 代码库 > codevs1230元素查找（hash）
codevs1230元素查找（hash）
1230 元素查找
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
给出n个正整数，然后有m个询问，每个询问一个整数，询问该整数是否在n个正整数中出现过。
输入描述 Input Description
第一行两个整数 n 和m。
第二行n个正整数（1<=n<= 100000）
第三行m个整数(1<=m<=100000)
输出描述 Output Description
一共m行，若出现则输出YES，否则输出NO
样例输入 Sample Input
4 2
2 1 3 4
1 9
样例输出 Sample Output
YES
NO
数据范围及提示 Data Size & Hint
所有数据都不超过10^8
两种哈希基本写法：
//哈希表#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <algorithm>#define MAXN 1000008#define MOD 1000007using namespace std;int hashTable[MAXN];void update(int x) //将数字x加入哈希表{ int num=x; x%=MOD; while(1) { if(!hashTable[x]) { hashTable[x]=num; return; } if(hashTable[x]!=num) { x++; if(x==MAXN) x=0; } else return; }}bool query(int x) //查找哈希表中是否有数字x{ bool found=false; int num=x; x%=MOD; while(1) { if(!hashTable[x]) return false; if(hashTable[x]!=num) { x++; if(x==MAXN) x=0; } else return true; }}int main(){ int n,m,x; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&x); update(x+1); } for(int i=1;i<=m;i++) { scanf("%d",&x); if(query(x+1)) printf("YES\n"); else printf("NO\n"); } return 0;}
//单模建边（这个题数据水）#include<iostream>using namespace std;const int maxn=500010;int n,m,tot,tmp,head[maxn];struct node{ int to; int next;}e[maxn];int get_hash(int x){ return x%10007;}void add_edge(int u,int v){ tot++; e[tot].to=v; e[tot].next=head[u]; head[u]=tot;}bool find(int u,int v){ for(int i=head[u];i;i=e[i].next) if(e[i].to==v)return 1; return 0;}int main(){ int x,y; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>tmp; x=get_hash(tmp); add_edge(x,tmp); } for(int i=1;i<=m;i++) { cin>>tmp; x=get_hash(tmp); if(find(x,tmp)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0;}
map水过...
#include<cstdio>#include<iostream> #include<map>using namespace std;map<int,int>ma;int n,m,a[100001],x;int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); ma[a[i]]=1; } for(int i=1;i<=m;i++) { cin>>x; if(ma[x]) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0;}
codevs1230元素查找（hash）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。