[python 刷题] 981 Time Based Key-Value Store

[python 刷题] 981 Time Based Key-Value Store

题目：

这是一道设计题，LC 提供的 boilerplate 为：

class TimeMap:

    def __init__(self):


    def set(self, key: str, value: str, timestamp: int) -> None:


    def get(self, key: str, timestamp: int) -> str:



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

在开始实现设计题之前，首先要确认应该选择什么数据结构，而这一点题目中也有提示：根据 key 获得对应的数据

也就是说，这里肯定是有 hash table 的一席之地。至于 hash table 里面要存储的是什么数据格式，这个可以从 constraint 里面看到：

• All the timestamps timestamp of set are strictly increasing.

也就是说，每次调用的 timestamp 都是持续增长的，也就是排序的。一个已经排好序的数据结构+搜索的题型，不出意外的就会联想到 binary search

也因此，初始化的数据结构可以定位 collections.defaultdict(list)

使用 defaultdict 的原因是因为处理空值方便一些

对于 set 这个方法来说，保存进数组的格式就没有这么严格了，只要能够获取时间戳和值就行。题目中已经提到了会严格增长，也就是说不会重复，那么使用 dict 也可以，这里就使用另一个数组了

最后就是 get，算是一个比较常规的寻找比 n n n 小的最大数字这种 binary search，也就是说：

• 找到 timestamp 时返回对应的数字

• 当前数字比 timestamp 大时， [ l , . . . , m − 1 ] [l, ..., m - 1] [l,...,m−1] 继续开始搜索

• 当前数字比 timestamp 小时， [ m + 1 , . . . , r ] [m + 1, ..., r] [m+1,...,r] 继续开始搜索

  同时为了防止等同时间戳的数字不存在，当前值为最贴近时间戳的值，更新 res 使得终止循环时可以返回当前值

完整代码如下：

class TimeMap:

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


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


    def get(self, key: str, timestamp: int) -> str:
        vals = self.d[key]
        l, r = 0,len(vals) - 1
        res = ''
        while l <= r:
            m = (l + r) // 2
            if vals[m][1] == timestamp:
                return vals[m][0]

            if vals[m][1] < timestamp:
                res = vals[m][0]
                l = m + 1
            else:
                r = m - 1

        return res