leetcode:981. 基于时间的键值存储【迭代for的陷阱：on】

分析

简单dict + 二分
however，要注意分两个dict

超时的陷阱：提取子元素的on

class TimeMap:

    def __init__(self):
        self.d = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append((timestamp, value))


    def get(self, key: str, timestamp: int) -> str:
        if key not in self.d:
            return ""
        if timestamp < self.d[key][0][0]:
            return ""
        lst = [item[0] for item in self.d[key]]
        idx = bisect_right(lst, timestamp)
        if idx == 0:
            return ""
        else:
            return self.d[key][idx - 1][1]



# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

ac code：分开记录

class TimeMap:

    def __init__(self):
        self.d1 = defaultdict(list)
        self.d2 = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d1[key].append(value)
        self.d2[key].append(timestamp)


    def get(self, key: str, timestamp: int) -> str:
    
        
        idx = bisect_right(self.d2[key], timestamp)
        if idx == 0:
            return ""
        else:
            return self.d1[key][idx - 1]



# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

总结

注意隐藏的on时间复杂度