| 题目链接 | 981. 基于时间的键值存储 |
|---|---|
| 思路 | 哈希+二分 |
| 题解链接 | 哈希表+二分 |
| 关键点 | 理解题意 |
| 时间复杂度 | \(O(\log n)\) |
| 空间复杂度 | \(O(n)\) |
代码实现：
class TimeMap:
def __init__(self):
self.dct = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.dct[key].append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
lst = self.dct[key]
left, right = -1, len(lst)
while left + 1 < right:
mid = (left + right) // 2
if lst[mid][0] > timestamp:
right = mid
else:
left = mid
if right == 0:
return ""
else:
return self.dct[key][right - 1][1]
Python-标准库
class TimeMap:
def __init__(self):
self.dct = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.dct[key].append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
upper_bound = bisect_right(self.dct[key], timestamp, key=lambda _: _[0])
if upper_bound == 0:
return ""
else:
return self.dct[key][upper_bound-1][1]