基于时间的键值存储

题目描述：

创建一个基于时间的键值存储类TimeMap，它支持下面两个操作：

1、set(string key, string value, int timestamp)

        ·存储值key、值value、以及给定的时间戳timestamp

2、get(string key, int timestamp)

        ·返回先前调用set(key, value, timestamp_prev)所储存的值，其中timestamp_prev<=timestamp。

        ·如果有多个这样的值，则返回对应最大的timestamp_prev的那个值。

        ·如果没有值，返回空字符串("")。

示例1：

输入：

inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]

输出：[null,null,"bar","bar",null,"bar2","bar2"]

说明：

TimeMap kv;

kv.set("foo", "bar", 1); # 存储键值“foo”和值“bar”以及时间戳=1

kv.get("foo", 1); # 输出“bar”

kv.get("foo", 3); # 输出“bar”，因为在时间戳3和时间戳2没有对应“foo”的值，所以输出时间戳1对应的“bar”

kv.set("foo", "bar2", 4);

kv.get("foo", 4); # 输出“bar2”

kv.get("foo", 5); # 输出“bar2”

示例2：

输入：

["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]

输出：[null,null,null,"","high","high","low","low"]

代码：

class TimeMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data1 = defaultdict(list)
        self.data2 = dict()
        


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


    def get(self, key: str, timestamp: int) -> str:
        temp = self.data1[key]
        left = 0
        right = len(temp) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if temp[mid] > timestamp:
                right = mid - 1
            else:
                left = mid + 1
        return self.data2[temp[right]] if right >= 0 else ''



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