4.散列的定义和整数散列

4.散列的定义和整数散列/哈希存储

例题1：

给N个整数，M个整数 问M个整数是否在N中出现过 其中N,M<100000 ;
直观思路：对于每个M中的元素 对N进行遍历，时间复杂度为O（NM），当N,M很大时，必定超时；

本节思路：利用空间换时间定义一个bool数组a【100100】=（false） ，输入数据时 a【x】=true
读数据是就开始处理，对于M中的元素 通过判断即可 时间复杂度O(N+M) ；

源代码：

#include <bits/stdc++.h>
using namespace std;
bool hashlist[100100]={false};
int main()
{
	int n,m,x;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		hashlist[x]=true;  //数字X出现过  
	}
	for(int i=0;i<m;i++)
	{
		cin>>x;
		if(hashlist[x]==true) cout<<"YES"<<endl;
		else cout<<"NO"<<endl; 
	}
	return 0;
}

例题2：

将上题改一下，如果M中的元素出现在N中，那么计算出M中的元素出现在N中的次数；

源代码：

#include <bits/stdc++.h>
using namespace std;
int hashlist[100100]={};   //换称int型
int main()
{
	int n,m,x;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		hashlist[x]++;  //数字X出现过  就+1 
	}
	for(int i=0;i<m;i++)
	{
		cin>>x;
		cout<<hashlist[x]<<endl; 
	}
	return 0;
}

---

以下是附加内容

其实例题里也可以把bool 换称int 然后初始化数组全为0；
然后出现过一次 将数据hashlist[x]=1; 置为1即真；
然后输出是判断是否是1.

#include <bits/stdc++.h>
using namespace std;
int hashlist[100100]={};
int main()
{
	int n,m,x;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		hashlist[x]=1;  //数字X出现过  
	}
	for(int i=0;i<m;i++)
	{
		cin>>x;
		if(hashlist[x]==1) cout<<"YES"<<endl;
		else cout<<"NO"<<endl; 
	}
	return 0;
}