Python：列表 vs 字典 vs 集合

Question

“什么数据结构——集合、列表或字典——在 Python 中你会用来存储 1000 万个整数？查询操作包括找到一个数字在给定集合中出现的次数。最坏情况下的时间和空间复杂度是多少？所有的情况？”

这是一个样本面试问题。什么是最合适的答案？

Answer 1

这个问题的关键是这句话：

“查找一个数字在给定集合中出现的次数”

集合数据结构将无法计算一个数字在整个数据集中出现的次数，并且一个 List 的迭代成本将非常高。这使得字典成为唯一可行的选择。

分解选项：

集合： 集合自动删除添加到已存在集合中的值。因此，不可能使用集合来查询某个数字在存储数据集中出现的频率，因为所有存储的数字的答案都是 1。

• 查询时间复杂度： O(1)
• 存储空间复杂度： O(n)

列表： 可以迭代列表以确定列表中给定数字的频率。然而，这将是 O(n) 操作，并且对于 1000 万个整数来说效率不高。

• 查询时间复杂度： O(n)
• 存储空间复杂度： O(n)

字典： 字典允许您存储键值对。在这种情况下，您会将要搜索的数字存储为键，并将它存储的次数作为关联值存储。由于字典将键散列到不同桶中的方式（可能存在冲突，但我们现在假设一个非冲突的理论字典），给定键的查找时间接近 O(1)。然而，计算计数会减慢字典的速度；计算所有键的计数需要 O(n) 时间复杂度（因为每个键必须至少被击中一次才能将它的计数附加到存储在值中的运行计数中）。

• 查询时间复杂度： O(1)
• 存储时间复杂度： O(n)
• 存储空间复杂度： O(2n) = O(n)