class RandomizedQueue:
def __init__(self, _iter):
self.arr = [*_iter]
def append(self, val):
self.arr.append(val)
def remove(self, idx):
if idx >= len(self.arr):
return
r = self.arr[idx]
self.arr[idx] = self.arr[-1] # 将最后一个元素移动到删除的元素位置
self.arr.pop()
return r
def getRandom(self):
if len(self.arr) == 0:
return
return self.arr[int(random.random() * len(self.arr))]
def popRandom(self):
if len(self.arr) == 0:
return
idx = int(random.random() * len(self.arr))
return self.remove(idx)
Data Structures - Randomized Queues