algorithm - 采访：建议一种优化插入、删除和随机值生成的数据结构

Question

建议一个可以优化以下所有 3 个操作的数据结构：

1. 插入
2. 删除
3. 从一组现有值中返回一个随机值

假设您要输入整数/数字。

Answer 1

所有三个操作的动态数组 + Hashmap = O(1)

• 插入

追加到数组 O(1) 的尾部，并将值索引对添加到 Hashmap O(1)。

• 删除

通过 Hashmap 中的值找到索引 O(1)，通过数组中的索引删除并将最后一个元素交换到插槽 O(1)，并更新（曾经是）最后一个元素的值索引对O(1)。

• 返回随机

为数组 O(1) 生成一个随机索引。

Answer 2

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
"""

查看 List 和 Dict 操作的时间复杂度以确认

（注意 pop 是 O(1)，因为我们从列表的末尾弹出）

Answer 3

使用具有开放寻址的哈希表。必要时通过重新散列将负载因子保持在 α 和 β 之间。为了避免振荡，重新散列到 α 和 β 之间的某个值。大多数开放散列方案的实现都要求表的大小合适，例如 2 或素数的幂。α 和 β 的典型值可能是 0.25 和 0.75，目标负载因子为 0.5。

除非负载因子接近 1，否则打开寻址的哈希表是 O(1) 查找，并且指数调整大小是摊销的 O(1)，因此插入是摊销的 O(1)。处理删除的最简单方法是惰性删除：已删除的元素被标记为已删除但未删除，因此可以在插入期间覆盖它们。同样，指数调整大小是摊销 O(1)，删除操作本身仅取决于查找。

随机选择完全绕过了散列机制，只是随机插入底层数组，直到找到未删除的记录。由于负载因子至少为 α，因此预期的刺入次数最多为 1/α，同样为 O(1)。