我需要使用平均支持恒定时间查找的数据结构。我认为使用std::unordered_map是一个好方法。我的数据是数字的“集合”。
|115|190|380|265|
这些数字不必按特定顺序排列。我需要有关于O(1)确定该数据结构中是否存在给定数字的时间。我有一个想法使用std::unordered_map，这实际上是一个哈希表（我对吗？）。所以数字将是键，然后我就只有虚拟值。
所以基本上我首先需要确定数据结构中是否存在与给定数字匹配的键，然后我根据该条件运行一些算法。与该条件无关，我还想更新一个特定的密钥。比方说190，我想添加20到它，所以现在的关键是210。
现在数据结构将如下所示：
|115|210|380|265|
我想这样做的原因是因为我有一个遍历二叉搜索树的递归算法。每个节点都有一个int value，以及两个指向左节点和右节点的指针。当到达叶节点时，我需要在“哈希表”数据结构中创建一个新字段来保存current_node->value。然后，当我在递归中返回树时，我需要将每个节点的值连续添加到存储在键中的上一个总和中。我的数据结构（我建议应该是std::unordered_map）有多个数字字段，因为它们中的每一个都代表从树上的叶节点到中间的某个节点的唯一路径。我检查从叶子到给定节点的路径上所有节点值的总和是否等于该节点的值。因此，基本上每个键都会添加节点的当前值，存储该路径上所有节点的总和。我需要扫描该数据结构以确定是否有任何一个字段或键等于当前节点的值。我还想在接近恒定的时间内将新值插入到数据结构中。这是为了竞争性编程，我会犹豫是否使用std::vector因为我认为查找一个元素并插入一个元素需要线性时间。那会搞砸我的时间复杂度。也许我应该使用除std::unordered_map?
您可以使用无序_映射::擦除 https://en.cppreference.com/w/cpp/container/unordered_map/erase and 无序_映射::插入 https://en.cppreference.com/w/cpp/container/unordered_map/insert更新密钥。平均时间复杂度为 O(1)(顺便说一句，最差的是 O(n))。如果你使用的是C++17，你也可以使用无序_映射::提取 https://en.cppreference.com/w/cpp/container/unordered_map/extract更新密钥。时间复杂度是一样的。
但是，由于您只需要一组数字，我认为无序集 https://en.cppreference.com/w/cpp/container/unordered_set更适合你的算法。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
