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

本文主要是介绍[python 刷题] 981 Time Based Key-Value Store，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目：

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the TimeMap class:

TimeMap() Initializes the object of the data structure.
void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

这是一道设计题，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$ 小的最大数字这种 binary search，也就是说：

找到 timestamp 时返回对应的数字
当前数字比 timestamp 大时， $[l, ..., m - 1]$ 继续开始搜索
当前数字比 timestamp 小时， $[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) - 1res = ''while l <= r:m = (l + r) // 2if vals[m][1] == timestamp:return vals[m][0]if vals[m][1] < timestamp:res = vals[m][0]l = m + 1else:r = m - 1return res