981. 基于时间的键值存储

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class TimeMap:
    # def __init__(self):
    #     self.tm = defaultdict(list)
    #     self.value = defaultdict(list)


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


    # def get(self, key: str, timestamp: int) -> str:
    #     if not self.tm[key]:
    #         return ""
    #     i = bisect.bisect_left(self.tm[key], timestamp)
    #     if 0<=i<len(self.tm[key]) and self.tm[key][i] == timestamp:
    #         return self.value[key][i]
    #     if 0<=i-1<len(self.tm[key]) and self.tm[key][i-1]<=timestamp:
    #         return self.value[key][i-1]
    #     return ""


    def __init__(self):
        self.timestamp_map = defaultdict(list)
        self.value_map = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        # timestamp 添加时 是单调递增的。
        self.value_map[key].append(value)
        self.timestamp_map[key].append(timestamp)

    def get(self, key: str, timestamp: int) -> str:
        if not self.timestamp_map[key]:
            return ""
        # 用二方法找到 前面一个 复合条件的位置。
        idx = bisect.bisect_left(self.timestamp_map[key],timestamp)
        if 0<=idx<len(self.timestamp_map[key]) and self.timestamp_map[key][idx]==timestamp:
            return self.value_map[key][idx]
        if 0<=idx-1<len(self.timestamp_map[key]) and self.timestamp_map[key][idx-1]<=timestamp:
            return self.value_map[key][idx-1]
        return ""


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