5

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

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

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

4

3 回答 3

11

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

  • 插入

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

  • 删除

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

  • 返回随机

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

于 2012-12-26T05:38:42.877 回答
3

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),因为我们从列表的末尾弹出)

于 2012-12-26T09:00:55.143 回答
2

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

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

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

于 2012-12-26T15:30:03.220 回答