本文正在参加「Python主题月」，详情查看 活动链接
题目描述
这是 LeetCode 上的 981. 基于时间的键值存储 ，难度为 中等。
Tag : 「设计数据结构」、「哈希表」、「数组」、「红黑树」
创建一个基于时间的键值存储类 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 <=
- TimeMap.set 和 TimeMap.get 函数在每个测试用例中将（组合）调用总计
120000次。
哈希表套数组
由于 timestamp 是严格递增，且没有删除 KV 的操作。
我们可以使用哈希表套数组的方式进行实现，从而达到均摊
的插入操作和
的查询操作。
具体的，为了方便理解，我们可以先建一个 Node 类，类中包含键值对和时间戳信息。
然后使用一个全局哈希表 map 记录某个 key 对应了哪些 Node。其中多个 Node 是以动态数组的形式进行「以 timestamp 升序」存储：
set操作：以
的复杂度找到某个key对应的数组，利用timestamp严格递增的特性，以 复杂度将新Node加入当前数组尾部；get操作：以
的复杂度找到某个key对应的数组，利用timestamp严格递增的特性，通过二分以 复杂度找到可能符合条件的Node。
Java 代码：
class TimeMap {
class Node {
String k, v;
int t;
Node (String _k, String _v, int _t) {
k = _k; v = _v; t = _t;
}
}
Map<String, List<Node>> map = new HashMap<>();
public void set(String k, String v, int t) {
List<Node> list = map.getOrDefault(k, new ArrayList<>());
list.add(new Node(k, v, t));
map.put(k, list);
}
public String get(String k, int t) {
List<Node> list = map.getOrDefault(k, new ArrayList<>());
if (list.isEmpty()) return "";
int n = list.size();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (list.get(mid).t <= t) {
l = mid;
} else {
r = mid - 1;
}
}
return list.get(r).t <= t ? list.get(r).v : "";
}
}
复制代码Python 3 代码：
class TimeMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.map = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.map[key].append((key,value,timestamp))
def get(self, key: str, timestamp: int) -> str:
if key not in self.map:
return ""
lt = self.map[key]
n = len(lt)
l, r = 0, n - 1
while l < r:
mid = l + r + 1 >> 1
if lt[mid][2] <= timestamp:
l = mid
else:
r = mid - 1
return lt[r][1] if lt[r][2] <= timestamp else ""
复制代码- 时间复杂度：
set操作的复杂度为
；get操作的复杂度为 - 空间复杂度：
哈希表套树
如果增加 del 操作呢？我们需要做出何种调整？
考虑在原题的基础上，增加一个 String del(String k, int t) 的功能：将严格等于键和时间戳的 KV 对删掉。
由于存在删除 KV 的动作，我们需要将实现从「哈希表套数组」改成「哈希表套树」，这里直接使用基于红黑树实现的 TreeMap 即可。
同时为了验证删除逻辑的正确性，我们在 get 动作发生前，先产生一次随机性的删除，删除后又重新插入。
Java 代码：
class TimeMap {
class Node {
String k, v;
int t;
Node (String _k, String _v, int _t) {
k = _k; v = _v; t = _t;
}
}
Map<String, TreeMap<Integer, Node>> map = new HashMap<>();
public void set(String k, String v, int t) {
update(k, t);
TreeMap<Integer, Node> ts = map.getOrDefault(k, new TreeMap<Integer, Node>());
ts.put(t, new Node(k, v, t));
map.put(k, ts);
}
Node _get(String k, int t) {
TreeMap<Integer, Node> ts = map.get(k);
if (ts == null) return null;
Map.Entry<Integer, Node> entry = ts.floorEntry(t);
if (entry == null) return null;
Node node = entry.getValue();
return node;
}
public String get(String k, int t) {
randomDel();
Node node = _get(k, t);
return node != null && node.t <= t ? node.v : "";
}
public String del(String k, int t) {
TreeMap<Integer, Node> ts = map.get(k);
if (ts == null) return null;
Map.Entry<Integer, Node> entry = ts.floorEntry(t);
if (entry == null) return null;
Node node = entry.getValue();
if (node != null && node.t == t) {
ts.remove(t);
return node.v;
}
return "";
}
List<String> allInfo = new ArrayList<>();
Random random = new Random();
// 保存所有的 kt 信息
void update(String k, int t) {
String nk = k + "_" + t;
allInfo.add(nk);
}
// 随机删除，再重新插入，验证代码正确性
void randomDel() {
int idx = random.nextInt(allInfo.size());
String[] ss = allInfo.get(idx).split("_");
String k = ss[0];
int t = Integer.parseInt(ss[1]);
Node node = _get(k, t);
del(node.k, node.t);
set(node.k, node.v, node.t);
}
}
复制代码Python 3 代码：
from sortedcontainers import SortedDict
class TimeMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.map = defaultdict(SortedDict)
def set(self, key: str, value: str, timestamp: int) -> None:
self.map[key][timestamp] = value
def get(self, key: str, timestamp: int) -> str:
if key not in self.map:
return ""
keys = self.map[key].keys()
idx = self.map[key].bisect_left(timestamp)
if idx == len(keys) or keys[idx] > timestamp:
idx -= 1
return self.map[key][keys[idx]] if idx >= 0 else ""
复制代码- 时间复杂度：
set操作的复杂度为
；get操作会完成随机删除/重新插入/查询的动作，复杂度均为为 ，整个get的复杂度仍是 （只是常数变大了） - 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.981 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
近期评论