PAT甲级 1078 哈希

原题链接

将一个由若干个不同正整数构成的整数序列插入到一个哈希表中，然后输出输入数字的位置。

哈希函数定义为 H(key)=key%TSize，其中 TSize 是哈希表的最大大小。

利用只具有正增量的二次探测法来解决冲突。

注意，哈希表的大小最好是素数，如果用户给出的最大大小不是素数，则必须将表大小重新定义为大于用户给出的大小的最小素数。

输入格式
第一行包含两个整数 MSize 和 N，分别表示用户定义的表的大小以及输入数字的数量。

第二行包含 N 个不同的正整数，数字之间用空格隔开。

输出格式
在一行中，输出每个输入数字的相应位置（索引从 0 开始），数字之间用空格隔开，行尾不得有多余空格。

如果无法插入某个数字，则输出 -。

数据范围
1≤MSize≤104,
1≤N≤MSize,
输入数字均在 [1,105] 范围内。

输入样例：
4 4
10 6 4 15
输出样例：
0 1 4 -

我的解法：

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int h[N];
int s, n;
bool is_prime(int n){
    if(n == 1) return false;
    for(int i = 2; i * i <= n; i ++ ){
        if(n % i == 0) return false;
    }
    return true;
}

int find(int t){
    int k = t % s;
    for(int i = 0; i < s; i ++ ){
        int j = (k + i * i) % s;
        if(h[j] == 0) return j;
    }
    return -1;
}

int main(){
    cin >> s >> n;
    while(!is_prime(s)) s ++;
    

    for(int i = 0; i < n ; i ++ ){
        int x;
        cin >> x;
        
        int t = find(x);
        if(t == -1) cout << "-";
        else{
            h[t] = x;
            cout << t;
        }
        if(i != n - 1) cout << ' ';
    }
    return 0;
}

收获：

哈希表解决冲突有两种方式，拉链法和开放寻址法，本题要求 正增量的二次探测法 ，让key + 1^2 、key+2^2、key+3^2依次寻找空位插入