Closed. This question is off-topic. It is not currently accepting answers. Learn more
想改进这个问题吗?Update the question所以堆栈溢出的值小于aa>。
考虑一个由4个字符串组成的大列表。
例如:['P0BH','LF3J','MA1Y','STSM','8Y74','JWBD']
我想以以下精确方式添加一个新字符串:
如果新字符串已经存在于给定列表中,则从列表中删除旧值,并将新字符串预置到列表的前面。例如,如果添加了字符串“MA1Y”,则输出列表将如下所示:
['ma1y'、'p0bh'、'lf3j'、'stsm'、'8y74'、'jwbd']。如果新的字符串不存在于列表中,那么只需将新字符串准备到前面。例如,如果添加了字符串“FSH7”,则输出列表将如下所示:[“FSH7”、“P0BH”、“LF3J”、“MA1Y”、“STSM”、“8Y74”、“JWBD”。
还有一个警告:算法必须在恒定的时间复杂度下运行。我不在乎空间的复杂性。
当然,我已经实现了一个解决方案,如下所示我相信它在不断的时间复杂中运行,但是我希望我们改进它或者重新设计一些更好的东西。我的理解是,一个映射有固定的时间删除、成员资格测试和分配**
tickerMap类中的addTicker方法是否在恒定时间内运行?

class tickersMap:
    def __init__(self, tickersList):
        self.Map = {t:i for i, t in enumerate(tickersList)}
        self.firstIndex = 0

    def addTicker(self, newTicker):
        if newTicker in self.Map:
            print('exists')
            del self.Map[newTicker]
            self.Map[newTicker] = self.firstIndex - 1
            self.firstIndex -= 1
        else:
            self.Map[newTicker] = self.firstIndex - 1
            self.firstIndex -= 1

    def listTickers(self):
        # This is O(nlog(n)) but is only required for printing
        return sorted(self.Map, key=self.Map.get)

最佳答案

你漏掉了一个日志细节。
而且,OrderedDict似乎很符合你的需要。
在我们分配了n个条目之后,赋值是o(1),只要n在那之后永远不会增长。但是,对于创建新分录的每个分配,它都被摊销为o(log n)。python每超过一次就加倍分配。如果你继续添加和删除而不增加N,则赋值为O(1)。
addTicker()可以有条件地del,然后无条件地执行最后两个语句,因为它们在任何情况下都是相同的。
o(n)注释应该是o(n logn),因为这是排序所需的时间,没有理由相信所有条目都已按排序顺序排列。

10-07 13:13
查看更多