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;
}