PAT甲级1145Hashing - Average Search Time

Posted on | | Visitors:
Words count in article: 743 字 | Reading time ≈ 3 分

题目链接

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/

欢迎讨论和交流!