python - Python：在O（logN）中计算具有给定值的字典中的项目数

Question

我想用给定的值计算字典中的项目数（假设字典中的值只是数字），我在网上搜索并找到了两种方法，第一种：

sum(x == chosen_value for x in d.values())

第二种方法是在Collections模块中使用Counter 。

但是，我认为这两种方法的运行时间都是O(N)，其中N是字典中的项目总数。我想找到一种方法来做到这一点O(logN)，这可能吗？

提前感谢您的任何帮助和建议！

更新：

感谢所有快速回复！它不能在O(logN). 我可以使用二叉树来存储（键，值）对。

Answer 1

不。为什么你会期望它是可能的？如果你有一个二叉搜索树，但字典是无序的，所以你必须遍历这些值。

Answer 2

如果您对这些值没有先验知识，则必须阅读给定字典中的每个值，这是正常情况。所以在通常情况下，它必须是O(N)。

Answer 3

您可以维护另一个将值映射到计数的字典。这将为您提供您在 O(1) 中寻求的计数。这个想法是实现一个像字典一样的高阶数据结构，但通过在内部维护另一个字典来增加返回值的计数的能力。

我意识到这可能不是你要问的。只是把它放在那里，只是机会渺茫。