散列

散列的定义与整数散列

问题一

给N个整数数，再给出M个整数，问这个M个数中的每个数分别是否在N个数中出现过，其中N，M

<=$10^5$105 ,且对所有正整数均不超过$10^5$105 。例如N=5，M=3，N个正整数为{8，3，7，6，2}，欲查询的M个正整数为{7，4，2}，于是后者中只有7和2在N个正整数中出现过，而4是没有出现过的。

思路：用空间换时间

#include<iostream>
using namespace std;
const int maxn=100010;
bool hashTable[maxn]={false};
int main()
{
	int n,m,x;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d", &x);
		hashTable[x]=true;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>x;
		if(hashTable[x]==true) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
 } 

同样的，如果题目要求M个欲查询的数中每个数在N个数中出现的次数，那么可以把hashTable数组替换为int型，然后在输入N个数时进行预处理，即当输入的为x时，就令hashTable[x]++,这样就可以用O（N+M）的时间复杂度输出每个欲查询的数出现的次数。代码如下：

#include<iostream>
using namespace std;
const int maxn=100010;
//bool hashTable[maxn]={false};
int hashTable[maxn]={0};
int main()
{
	int n,m,x;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		hashTable[x]++;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>x;
		cout<<hashTable[x]<<endl;
	}
	return 0;
}