建议一个可以优化以下所有 3 个操作的数据结构:
- 插入
- 删除
- 从一组现有值中返回一个随机值
假设您要输入整数/数字。
所有三个操作的动态数组 + Hashmap = O(1)
追加到数组 O(1) 的尾部,并将值索引对添加到 Hashmap O(1)。
通过 Hashmap 中的值找到索引 O(1),通过数组中的索引删除并将最后一个元素交换到插槽 O(1),并更新(曾经是)最后一个元素的值索引对O(1)。
为数组 O(1) 生成一个随机索引。
python中的O(1):
from collections import defaultdict
from random import choice
class DataStructure(list):
def __init__(self):
self.values = []
self.locations = defaultdict(list)
def add(self, val):
i = len(self.values)
self.locations[val].append(i)
self.values.append(val)
assert self.values[i] == val
def delete(self, val):
locations = self.locations[val]
if locations:
i = locations.pop()
self.values[i] = self.values[-1]
self.values.pop()
def random(self):
return choice(self.values)
ds = DataStructure()
ds.add(3)
ds.add(5)
print ds.random()
print ds.random()
print ds.random()
print ds.random()
ds.delete(5)
print ds.random()
ds.delete(3)
"""
5
3
3
5
3
"""
(注意 pop 是 O(1),因为我们从列表的末尾弹出)
使用具有开放寻址的哈希表。必要时通过重新散列将负载因子保持在 α 和 β 之间。为了避免振荡,重新散列到 α 和 β 之间的某个值。大多数开放散列方案的实现都要求表的大小合适,例如 2 或素数的幂。α 和 β 的典型值可能是 0.25 和 0.75,目标负载因子为 0.5。
除非负载因子接近 1,否则打开寻址的哈希表是 O(1) 查找,并且指数调整大小是摊销的 O(1),因此插入是摊销的 O(1)。处理删除的最简单方法是惰性删除:已删除的元素被标记为已删除但未删除,因此可以在插入期间覆盖它们。同样,指数调整大小是摊销 O(1),删除操作本身仅取决于查找。
随机选择完全绕过了散列机制,只是随机插入底层数组,直到找到未删除的记录。由于负载因子至少为 α,因此预期的刺入次数最多为 1/α,同样为 O(1)。