基于时间的键值存储

难度: Medium

设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。

实现 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：

输入：
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
输出：
[null, null, "bar", "bar", null, "bar2", "bar2"]

解释：
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // 存储键 "foo" 和值 "bar" ，时间戳 timestamp = 1   
timeMap.get("foo", 1);         // 返回 "bar"
timeMap.get("foo", 3);         // 返回 "bar", 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"） 。
timeMap.set("foo", "bar2", 4); // 存储键 "foo" 和值 "bar2" ，时间戳 timestamp = 4  
timeMap.get("foo", 4);         // 返回 "bar2"
timeMap.get("foo", 5);         // 返回 "bar2"

提示：

1 <= key.length, value.length <= 100
key 和 value 由小写英文字母和数字组成
1 <= timestamp <= 10⁷
set 操作中的时间戳 timestamp 都是严格递增的
最多调用 set 和 get 操作 2 * 10⁵ 次

Submission

运行时间: 266 ms

内存: 66.7 MB

import bisect
class TimeMap:
    def __init__(self):
        self.data = dict()
    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.data:
            self.data[key] = ([],[])
        self.data[key][0].append(timestamp)
        self.data[key][1].append(value)
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.data:
            return ""
        index = bisect.bisect_right(self.data[key][0], timestamp)
        if index > 0:
            return self.data[key][1][index-1]
        else:
            return ""



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

Explain

这个题解使用哈希表加列表的方式来存储键值对和对应的时间戳。对于每个键，哈希表存储一个元组，元组包含两个列表：一个存储时间戳，另一个存储对应的值。当 set 方法被调用时，将时间戳追加到第一个列表，将值追加到第二个列表。当 get 方法被调用时，使用二分查找在时间戳列表中找到小于等于给定时间戳的最大时间戳的位置，然后返回值列表中对应位置的值。如果没有找到，则返回空字符串。

时间复杂度: set: O(1), get: O(log n)

空间复杂度: O(n)

import bisect
class TimeMap:
    def __init__(self):
        # 初始化一个空的哈希表
        self.data = dict()
    def set(self, key: str, value: str, timestamp: int) -> None:
        # 如果 key 不在 data 中，初始化对应的两个空列表
        if key not in self.data:
            self.data[key] = ([],[])
        # 将时间戳追加到 key 对应的第一个列表
        self.data[key][0].append(timestamp)
        # 将值追加到 key 对应的第二个列表
        self.data[key][1].append(value)
    def get(self, key: str, timestamp: int) -> str:
        # 如果 key 不存在，返回空字符串
        if key not in self.data:
            return ""
        # 在时间戳列表中二分查找小于等于给定时间戳的最大时间戳的位置 
        index = bisect.bisect_right(self.data[key][0], timestamp)
        # 如果找到了有效位置，返回对应的值
        if index > 0:
            return self.data[key][1][index-1]
        # 否则返回空字符串
        else:
            return ""

Explore

哈希表和列表组合被选择是因为它们提供了高效的查找和插入性能。使用哈希表可以快速定位到具体的键，而列表用来保持时间戳和值的顺序关系，从而支持高效的时间查询。此外，由于时间戳是单调递增的，列表的末尾插入操作的时间复杂度为O(1)。相比之下，使用平衡树虽然可以在O(log n)时间内完成查找和插入，但实现复杂且常数因子较大。堆结构不适合这种类型的问题，因为堆主要用于维护最大或最小元素，而不是维护一个有序序列供随机访问。

`bisect_right`函数返回的是插入点后的位置，这意味着返回的索引指向列表中第一个大于给定时间戳的元素位置。在时间戳列表中使用`bisect_right`可以确保我们找到的是小于等于给定时间戳的最大时间戳的正确位置。如果使用`bisect_left`，则可能会得到一个小于指定时间戳的最近时间戳的位置，这在时间戳正好等于列表中某个时间戳时不会返回最正确的结果。因此，使用`bisect_right`更符合这个场景的需求，可以确保即使在多个相同时间戳的情况下也能找到最后一个满足条件的值。