我需要设计一个支持以下内容的数据结构:
getMinElementgetLastElementinsertElementdeleteLastElement-在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/

10-11 23:02
查看更多