难度：★★★☆☆
类型：数组
方法：二分法
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
创建一个基于时间的键值存储类 TimeMap，它支持下面两个操作：
- set(string key, string value, int timestamp)
存储键 key、值 value，以及给定的时间戳 timestamp。
- 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" 以及时间戳 timestamp = 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：
输入：inputs = ["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"]
提示：
所有的键/值字符串都是小写的。
所有的键/值字符串长度都在 [1, 100] 范围内。
所有 TimeMap.set 操作中的时间戳 timestamps 都是严格递增的。
1 <= timestamp <= 10^7
TimeMap.set 和 TimeMap.get 函数在每个测试用例中将（组合）调用总计 120000 次。
解答
先来说明一下需要构造的数据结构是一个什么字典，我们传统的字典就是键值对，这里的字典，键还是那个键，值不一样了，这里的值是带着时间戳的，从现象上看，每一次值的更改，都会保存一个历史记录，记录了每次增添或修改的时间戳以及修改内容。
时间戳的特点是排序的，因此我们在查询的过程中，可以利用二分搜索加速查找的过程。准备一个字典，字典的值是列表的形式，列表中包含若干元组，每个元素包含时间戳以及修改值，这样保存，是为了在查询并排序的过程中，按时间戳优先排序，并按时间戳的排序结果给出查询结果。
在编码上，我们巧妙的使用defaultdict来解决字典默认值的问题，使用bisect_right进行快速的二分查找，注意查找的结果需要减一才是需要返回的数值。
from bisect import bisect_right
from collections import defaultdict
class TimeMap(object):
def __init__(self):
self.dct = defaultdict(list)
def set(self, key, value, timestamp):
self.dct[key].append((timestamp, value))
def get(self, key, timestamp):
time_value_pairs = self.dct[key]
i = bisect_right(time_value_pairs, (timestamp, "z")) - 1
return time_value_pairs[i][1] if i >= 0 else ""
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
网友评论