signed

QiShunwang

“诚信为本、客户至上”

[哈希表/map数组] AcWing840.模拟散列表

2020/12/27 16:27:09   来源:

AcWing840.模拟散列表

[题目描述]
维护一个集合,支持如下几种操作:

  1. “I x”,插入一个数x;
  2. “Q x”,询问数x是否在集合中出现过;

现在要进行N次操作,对于每个询问操作输出对应的结果。
输入格式

第一行包含整数N,表示操作数量。

接下来N行,每行包含一个操作指令,操作指令为”I x”,”Q x”中的一种。
[输出格式]

对于每个询问指令“Q x”,输出一个询问结果,如果x在集合中出现过,则输出“Yes”,否则输出“No”。

每个结果占一行。
[数据范围]

1≤N≤105

−109≤x≤109

[输入样例]:

5
I 1
I 2
I 3
Q 2
Q 5

[输出样例]:

Yes
No

(一)暴力二分,遍历一遍,一种普通的方法。

(二)如果操作数很小,我们可以开个桶来计数。相似地,map数组却能开一个无限制的空间。

#include<bits/stdc++.h>
using namespace std;   
map<int,bool>mapp;
int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		char s;
		long long x;
		cin>>s;
		scanf("%lld",&x);
		if(s=='I')
		{
			mapp[x]=1;
		}
		else 
		{
			if(mapp[x]==1)puts("Yes");
			else puts("No");
		}
	}
	return 0;
}

(三)哈希表 一种投影的思想

我们要在一个长度为n的随机整数序列A中统计一个数是否出现,可以直接建立一个数组计数(建立一个大小等于值域的数组进行映射和统计,就是简单的Hash思想)
设计Hash函数为ha(x)=(x mod p)+1,其中p较大。就能把A分成p类。把A[i]定位到h[ha(x)]的链表,然后查找数所在的链表是否包含该数即可,每次操作时间复杂度期望为O(1),整个算法复杂度优化到O(n)。

#include<bits/stdc++.h>
using namespace std;   
const int mod=100010,N=100005; 
int h[mod+5],to[N],nex[N],cnt; 
void add(int x)
{
	int u=(x%mod+mod)%mod;  //注意x可能为负数 ,所以u不能直接为x对mod取模 
	to[++cnt]=x;            //在h[u]中加点连边 
	nex[cnt]=h[u];
	h[u]=cnt; 
}
bool find(int x)
{
	int u=(x%mod+mod)%mod;
	for(int i=h[u];i;i=nex[i])
	 if(to[i]==x)return 1;
	return 0; 
 } 
int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		char s;
		long long x;
		cin>>s;
		scanf("%lld",&x);
		if(s=='I') add(x);
		else 
		{
			bool b=find(x);
			if(b==1)puts("Yes");
			else puts("No"); 
		}
	}
	return 0;
}