我必须插入 K 个数字，范围从 0 到 10^9。稍后我想知道我是否插入了特定号码。这里 K 的范围从 0 到 10^5。
插入和删除都必须在常数时间内。我看过 C++ STL unordered_map。但是 unordered_map 需要两个参数。我只想插入一个数字，而不是键值对。
我可以简单地使用像这样的 bool 数组
bool numberExists[1000000000];
但是将它初始化为 false 会花费很多时间。 如前所述，我想要恒定的时间插入和查找。
我应该使用什么数据结构...？
最佳答案
But unordered_map requires two parameters. I just want to insert a number not a key-value pair.
那么你应该使用 std::unordered_set<int> : 它提供恒定时间查找和摊销恒定时间插入和删除。
如果您正在寻找最坏情况下的常数时间插入和查找，您需要 std::vector<bool> 甚至 std::bitset<N> .但是请注意，迭代所有元素所需的时间是 O(MAX)，而不是 O(N)，后者可能会更糟。
关于c++ - 固定时间查找插入的数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27796288/