⭐⭐⭐⭐⭐PAT A1145 Hashing - Average Search Time

题目描述

知识点

hash，二次探测法

实现

码前思考

1. 这道题目我不会，因为我不知道什么叫做 Quadratic probing (with positive increments only) ，后来查阅了《算法笔记》，发现了是 hash 中常用二次探测法的意思。而且这里还是只要正数的二次探测法。

代码实现

//需要回顾hash的相关知识
//有疑问，后面做
#include "bits/stdc++.h"
using namespace std;

int msize;
int n;
int m;
vector<int> hashTable; 
int cnt;
bool isPrime(int x){
	if(x <= 1){
		return false;
	}
	//首先求根号
	int sqr = (int) sqrt(1.0*x) + 1;
	for(int i=2;i<=sqr;i++){
		if(x%i == 0){
			return false;
		}
	}
	return true; 
}

void insert(int x){
	//记录插入的次数
	for(int k=0;k<msize;k++){
		int pos = (x+k*k)%msize;
		if(hashTable[pos] == -1){
			hashTable[pos] = x;
			return;
		}
	}
	
	//那么进行输出
	printf("%d cannot be inserted.\n",x); 
}

void find(int x){
	//记录插入的次数
	int k;
	for(k=0;k<=msize;k++){
		cnt++;
		int pos = (x+k*k)%msize;
		if(hashTable[pos] == x || hashTable[pos] == -1){
			return;
		}
	}
}

int main(){
	scanf("%d%d%d",&msize,&n,&m);
	
	//首先判断是否是质数
	while(!isPrime(msize)){
		msize++;
	}
	//初始化值全部为-1，因为输入的都是正整数 
	hashTable.assign(msize,-1);

	//读入数据进行hash
	for(int i=0;i<n;i++){
		int cur;
		scanf("%d",&cur);
		//设置一个insert函数
		insert(cur); 
	}
	
	//然后进行查找比较 
	cnt=0;
	for(int i=0;i<m;i++){
		int target;
		scanf("%d",&target);
		find(target);
	} 
	
	printf("%.1f\n",(cnt*1.0)/m);
		 
	
	return 0;
} 

码后反思

1. 很奇怪，这里在插入的时候k<msize，而在查询的时候k<=msize。这样才能得到答案，不然gg；
2. 我之前把hashTable.assign(msize,-1);写成了hashTable.assign(n,-1);，因此死活都找不出bug，我太难了！
3. 判断质数时，一定要加上n<=1的情况。
4. 注意组后要求保留1位小数点，直接使用%.1f即可。