1.题目基本信息
1.1.题目描述
设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。
实现 TimeMap 类：
- TimeMap() 初始化数据结构对象
- void set(String key, String value, int timestamp) 存储给定时间戳 timestamp 时的键 key 和值 value。
- String get(String key, int timestamp) 返回一个值，该值在之前调用了 set，其中 timestamp_prev <= timestamp 。如果有多个这样的值，它将返回与最大 timestamp_prev 关联的值。如果没有值，则返回空字符串（""）。
1.2.题目地址
https://leetcode.cn/problems/time-based-key-value-store/description/
2.解题方法
2.1.解题思路
数据结构设计+哈希表+二分查找
2.2.解题步骤
第一步，设计存储数据结构tMap并构建set函数，这里采用哈希表设计存储结构，键为传入的key，值为二维数组arr，arr[0]记录timestamp，arr[1]记录传入的value值。
第二步，构建get函数，如果key不在哈希表中，直接返回空字符串；如果存在key关键字，则获取tMap[key][0]，即key对应的所有时间戳数组，这个时间戳数组一定是升序排列的，所以可以采用二分查找的方法。需要找到最后一个小于等于timestamp的索引r，其对应的值即为最终结果，该值也可能不存在，即r=-1，使用二分查找的红蓝染色法（左开右开区间）很容易可以获取r的值，最终如果r=-1，则返回空字符串，否则返回tMap[key][1][r]，即r对应的值。
3.解题代码
Python代码
# 数据结构设计+哈希表+二分查找
# 第一步，设计存储数据结构tMap并构建set函数，这里采用哈希表设计存储结构，键为传入的key，值为二维数组arr，arr[0]记录timestamp，arr[1]记录传入的value值。
# 第二步，构建get函数，如果key不在哈希表中，直接返回空字符串；如果存在key关键字，则获取tMap[key][0]，即key对应的所有时间戳数组，这个时间戳数组一定是升序排列的，所以可以采用二分查找的方法。需要找到最后一个小于等于timestamp的索引r，其对应的值即为最终结果，该值也可能不存在，即r=-1，使用二分查找的红蓝染色法（左开右开区间）很容易可以获取r的值，最终如果r=-1，则返回空字符串，否则返回tMap[key][1][r]，即r对应的值。
class TimeMap:
def __init__(self):
self.tMap={}
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.tMap:
self.tMap[key]=[[timestamp],[value]]
else:
self.tMap[key][0].append(timestamp)
self.tMap[key][1].append(value)
def get(self, key: str, timestamp: int) -> str:
if key not in self.tMap:
return ""
# 找最后一个小于等于timestamp的索引r，该值可能不存在
# 红：小于等于timestamp，蓝：大于timestamp；left：指向红色，right：指向蓝色；最终的left即为r
tArr=self.tMap[key][0]
length=len(tArr)
left,right=-1,length
while left+1<right:
mid=(right-left)//2+left
if tArr[mid]<=timestamp:
left=mid
else:
right=mid
return "" if left==-1 else self.tMap[key][1][left]
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)
4.执行结果
