恒定时间查找插入的数字

Question

我必须插入 K 个数字，范围从 0 到 10^9。后来我想知道我是否插入了特定的号码。这里K的范围是0到10^5。

插入和删除都必须在恒定时间内进行。我看过 C++ STL unordered_map。但unordered_map需要两个参数。我只想插入一个数字而不是key-value pair.

我可以简单地使用一系列布尔值，例如

bool numberExists[1000000000];

但将其初始化为 false 会花费很多时间。正如所说，我想要恒定的时间插入和查找。

我应该使用什么数据结构...？

Answer 1

但 unordered_map 需要两个参数。我只想插入一个数字而不是键值对。

那么你应该使用std::unordered_set<int>：它提供恒定时间查找以及分摊恒定时间插入和删除。

如果您正在寻找最坏情况的恒定时间插入和查找，您std::vector<bool>甚至需要 或std::bitset<N>。但请注意，迭代其所有元素所需的时间是 O(MAX)，而不是 O(N)，后者可能会更糟。