这是"算法设计手册"一书中的练习(3-15).
设计一种数据结构,允许用户在O(1)时间内搜索,插入和删除整数X(即,恒定时间,与存储的整数总数无关).假设1≤X≤n并且有m + n个可用空间单位,其中m是任何时候表中可以包含的最大整数数.(提示:使用两个数组A [1..n]和B [1..m].)不允许初始化A或B,因为这将执行O(m)或O(n)操作.这意味着阵列中充满了随机垃圾,所以你必须非常小心.
我并不是真的想要答案,因为我甚至不明白这个练习是什么问题.
从第一句话开始:
设计一种数据结构,允许用户在O(1)时间内搜索,插入和删除整数X.
我可以轻松地设计这样的数据结构.例如:
因为1 <= X <= n,所以我只有n个槽的位向量,并且让X为数组的索引,当插入时,例如5,则a [5] = 1; 当删除时,例如5,则a [5] = 0; 当搜索,例如5,那么我可以简单地返回[5],对吗？
我知道这个练习比我想象的要难,但这个问题的关键点是什么？
输入random.choice应该是一个序列。这会导致 a 出现奇怪的行为dict，它不是序列类型，但可以像下面这样使用下标：
>>> d = {0: 'spam', 1: 'eggs', 3: 'potato'}
>>> random.choice(d)
'spam'
>>> random.choice(d)
'eggs'
>>> random.choice(d)
'spam'
>>> random.choice(d)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/usr/lib/python2.7/random.py", line 274, in choice
return seq[int(self.random() * len(seq))] # raises IndexError if seq is empty
KeyError: 2
此外，random.choice它根本不适用于set和collections模块中的其他一些容器。
有充分的理由吗random.choice(d)不应该以明显的方式工作，返回随机密钥？
我考虑过random.choice(list(d))，random.sample(d, 1)[0]但希望有更有效的方法。可以random.choice在不降低序列当前行为的情况下进行改进吗？
我知道您可以通过多种方式从字典中选择随机值.
在Python 2中:
random.choice(d.keys())
在Python 3中:
random.choice(list(d.keys()))
尽管如此,两种方法都需要在随机选择之前将变换(即线性时间O(n))转换为列表.例如,我知道在Python 3中d.keys()返回一个迭代器,我猜测在Python 3中,列表是从字典内部创建的.
是否可以在恒定时间内从字典中选择一个值,即O(1)？
编辑:到目前为止的评论,我认为这是不可能的,至少不是直截了当的方式.需要辅助结构.
编辑2:我认为字典可以在恒定时间内随机选择,因为内部它是一个哈希表,即内部它必须有一个数组或类似的东西.当然,这取决于内部实现,但理论上我认为这是可能的.