用于检查容器中是否存在项的一种存储项的优雅方式

Question

在我遇到的情况下，我想将"优雅"定义为具有1)常数O(1)时间复杂度用于检查项是否存在，2)仅存储项，没有其他。

例如，如果我使用列表

num_list = []
for num in range(10): # Dummy operation to fill the container.
    num_list += num
if 1 in num_list:
    print("Number exists!")

操作"in"将占用 0 (n)时间根据[Link]

为了实现恒定的检查时间，我可以使用字典

num_dict = {}
for num in range(10): # Dummy operation to fill the container.
    num_dict[num] = True
if 1 in num_dict:
    print("Number exists!")

在字典的情况下，根据[Link]，操作"In"花费O(1)时间，但是需要额外的O(n)存储来存储虚拟值。因此，这两种实现/容器看起来都不优雅。

什么是更好的实现/容器来实现恒定的O(1)时间来检查项目是否存在，而只存储项目?如何将资源需求保持在最低限度?

Answer 1

这里的解决方案是使用set，它不需要为每个值保存一个虚拟变量。

Answer 2

通常你不能同时优化空间和时间。您可以做的一件事是获得更多关于数据范围(这里是num的最小到最大值)和数据大小(这里是循环运行的次数)的详细信息。, 10)。那么您将有两个选项:

1. 如果范围有限，则使用字典方法(甚至使用数组索引方法)
2. 如果大小有限，则使用列表方法。

如果你选择正确的方法，那么你可能会获得恒定的时间和空间对于大样本

编辑:组它是一个哈希表，实现方式与Python字典非常相似，并进行了一些优化，利用了值总是为空的事实(在集合中，我们只关心键)。集合操作确实需要迭代至少一个操作数表(在联合的情况下都是如此)。迭代并不比任何其他集合(O(n))便宜，但成员测试平均为O(1)。