官方题解｜线性探查法

题目解析

我们考虑维护所有的为空的单元；对于「线性探测法」本质上就是找到 第一个大于等于 $X$ 的空单元，若不存在这样的空单元，则寻找 第一个大于等于 $0$ 的空单元。

那么我们可以考虑使用 std::set 来维护所有的 $N$ 个空单元，并使用 std::map 来记录所有已经插入哈希表的元素分配到的位置即可。

时间复杂度：$\mathrm{O}(Q\log{N})$。

AC代码

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int n, q;
    std::cin >> n >> q;
    std::set<int> a;
    std::map<i64, int> mp;
    for (int i = 0; i < n; ++i)
        a.insert(i);
    while (q--) {
        i64 x; std::cin >> x;
        if (!mp.count(x)) {
            auto p = a.lower_bound(x % n);
            if (p == a.end()) p = a.lower_bound(0);
            mp[x] = *p;
            a.erase(p);
        }
        std::cout << mp[x] << '\n';
    }
    return 0;
}