PAT甲级1145Hashing - Average Search Time

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805343236767744

题解

基础知识:哈希

为做这道题,我简单复习了一下哈希(点击查看)

题目要求

往一个哈希表里插入n个正整数,然后从哈希表里查找m个正整数,请输出平均查找次数(即比较次数)

哈希函数定义为$H(key)= key \% TSize$,其中$TSize$是哈希表的最大容量,它最好是素数,如果输入的不是素数就必须找到大于输入的最小素数。

用二次探测(仅具有正增量)解决冲突。

英语

  • distinct

    截然不同的, 完全分开的

  • sequence

    有关联的一组事物, 一连串

  • quadratic

    二次的,二次方程式

  • probe

    n. 探针;调查
    vi. 调查;探测
    vt. 探查;用探针探测

  • collision

    碰撞, 冲突, 抵触

  • Quadratic probing (with positive increments only) is used to solve the collisions.

    二次探测(仅具有正增量)用于解决冲突。

  • synonym

    同义词

  • accurate up to 1 decimal place

    精确到小数点后1位

注意点

  • 待查找的元素可能不存在
  • 题目说了输入的关键字都是整数,所以可以把0作为表中某个位置没有元素的标志
  • 注意这里的二次探测再散列只有正增量
  • 查找时间指查找时进行比较的次数,如果没有再探测(即一次就找到了),那比较次数就是1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Problem: PAT Advanced 1145
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805343236767744
// Tags: Hash

#include <iostream>
#include <vector>
using namespace std;

bool isPrime(int num){
if (num < 2)
return false;
for (int i = 2; i * i <= num; i++)
if (num % i == 0)
return false;
return true;
}

int main()
{
// 获取输入的第一行
int mSize, n, m; // 哈希表最大容量、输入的整数的数量、待查找的整数的数量,都不超过1e4
cin >> mSize >> n >> m;

// 建立哈希表
while (!isPrime(mSize)) mSize++; // 使哈希表表长为大于等于输入的最小素数
vector<int> hashTable(mSize); // 哈希表
int key, pos; // 关键字、哈希地址
bool posFound; // 某个key的位置是否找到了
for (int i=0; i < n; i++){
cin >> key; // 获取关键字
posFound = false;
for (int j = 0; j < mSize; j++){ // 二次探测再散列(只有正增量)
pos = (key + j * j) % mSize;
if (hashTable[pos] == 0){ // 这要求key不为0
hashTable[pos] = key;
posFound = true;
break;
}
}
if (!posFound) printf("%d cannot be inserted.\n", key);
}

// 查找元素并统计平均查找次数
double count = 0;
for (int i = 0; i < m; i++){
cin >> key;
for (int j = 0; j <= mSize; j++){ // 题目似乎有问题,应该是j<mSize的,而不是<=
pos = (key + j * j) % mSize;
count += 1;
if (hashTable[pos] == key || hashTable[pos] == 0) // 注意待查找的元素可能不存在
break;
}
}
printf("%.1f", count / m);
return 0;
}

作者:@臭咸鱼

转载请注明出处:https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!