我需要设计一个支持以下内容的数据结构:getMinElement
,getLastElement
,insertElement
,deleteLastElement
-在O(1)
运行时。
内存是由n(不是o(n))限定的,即在给定时刻最多可以保留n个元素。加上O(1)内存。
(重要提示:指针也被视为1,因此例如链表是不可能的)。
例子:
insert(6)
min() -> 6
insert(10)
insert(5)
min() -> 5
insert(7)
delete()
min() -> 5
delete()
min() -> 6
最佳答案
我们将直接存储最近的最小值。这是O(1)空间。
我们还将使用一个整数数组,因为这似乎是我们对可变长度空间的唯一选择但我们不会直接存储元素。相反,当我们插入一个元素时,我们将存储该元素和(先前的)最小值之间的差异当我们删除一个元素时,如果需要的话,我们可以使用这个差异来恢复之前的最小值。
在python中:
class MinStorage:
def __init__(self):
self.offsets = []
self.min = None
def insertElement(self, element):
offset = 0 if self.min is None else (element - self.min)
self.offsets.append(offset)
if self.min is None or offset < 0:
self.min = element
def getMinElement(self):
return self.min
def getLastElement(self):
offset = self.offsets[-1]
if offset < 0:
# Last element defined a new minimum, so offset is an offset
# from the prior minimum, not an offset from self.min.
return self.min
else:
return self.min + offset
def deleteLastElement(self):
offset = self.offsets[-1]
self.offsets.pop()
if len(self.offsets) == 0:
self.min = None
if offset < 0:
self.min -= offset
下面的版本允许任何无符号16位整数作为元素,并且只在数组中存储无符号16位整数:
class MinStorage:
Cap = 65536
def __init__(self):
self.offsets = []
self.min = None
def insertElement(self, element):
assert 0 <= element < self.Cap
offset = 0 if self.min is None else (element - self.min)
if offset < 0: offset += self.Cap
self.offsets.append(offset)
if self.min is None or element < self.min:
self.min = element
def getMinElement(self):
return self.min
def getLastElement(self):
element = self.__getLastElementUnchecked()
if element < self.min:
# Last element defined a new minimum, so offset is an offset
# from the prior minimum, not an offset from self.min.
return self.min
else:
return element
def deleteLastElement(self):
element = self.__getLastElementUnchecked()
self.offsets.pop()
if len(self.offsets) == 0:
self.min = None
elif element < self.min:
# Popped element defined a new minimum.
self.min = element
def __getLastElementUnchecked(self):
offset = self.offsets[-1]
element = self.min + offset
if element >= self.Cap:
element -= self.Cap
return element
请注意,在一种使用无符号16位算术(在溢出/下溢时换行)的语言中,不需要涉及
self.Cap
的检查和调整在C(第5.2.5/9)和C++(第3.9/4)中,需要根据需要进行无符号算术运算。但是,Python不支持无符号16位算术。关于algorithm - 设计一个数据结构,该结构在O(1)中支持min,getLast,append,deleteLast,内存以n(不是O(n))+ O(1)为界,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/32078681/