跳转到内容

怎样实现插入、删除和等概率随机取值平均 O(1) 的集合?

用数组保存元素,用哈希表记录“元素 → 数组下标”。数组便于等概率选下标,哈希表便于定位。删除时把末尾元素搬到被删位置,再弹出末尾,就不用移动后面所有元素。

例如,数组是 [10, 20, 30],删除 20 后变成 [10, 30],同时把哈希表中 30 的下标改为 1。这里不要求保留插入顺序。

import random
class RandomizedSet:
def __init__(self):
self.values = []
self.index = {}
def insert(self, value):
if value in self.index:
return False
self.index[value] = len(self.values)
self.values.append(value)
return True
def remove(self, value):
if value not in self.index:
return False
position = self.index[value]
last = self.values[-1]
self.values[position] = last
self.index[last] = position
self.values.pop()
del self.index[value]
return True
def get_random(self):
if not self.values:
raise IndexError("集合为空")
return random.choice(self.values)

每个元素在数组中只占一个位置,因此均匀选下标就是等概率选元素。哈希操作是平均 O(1),数组追加是均摊 O(1),不能承诺所有单次操作最坏 O(1)。空间 O(n)。删除末尾或唯一元素也适用;代码不支持多线程同时修改。

资料

LeetCode 380 的标准题面。原帖报告“纯随机取值、增删 O(1)”;这里明确平均复杂度和等概率要求,代码为本站编写。