| 题目链接 | 1146. 快照数组 |
|---|---|
| 思路 | 哈希+二分法 |
| 题解链接 | 记录修改历史：哈希表+二分查找（Python/Java/C++/Go/JS/Rust） |
| 关键点 | 理解题意：查询时要找到<=snap_id的最后一次修改记录 |
| 时间复杂度 | \(O(\log n)\) |
| 空间复杂度 | \(O(n)\) |
代码实现：
class SnapshotArray:
def __init__(self, length: int):
self.snap_id = 0
self.history = defaultdict(list)
def set(self, index: int, val: int) -> None:
self.history[index].append((self.snap_id, val))
def snap(self) -> int:
snap_id = self.snap_id
self.snap_id += 1
return snap_id
def get(self, index: int, snap_id: int) -> int:
# 找快照编号 <= snap_id 的最后一次修改记录
# 等价于找快照编号 >= snap_id+1 的第一个修改记录，它的上一个就是答案
history = self.history[index]
target = snap_id + 1
left, right = -1, len(history)
while left + 1 < right:
mid = (left+right) // 2
if history[mid][0] < target:
left = mid
else:
right = mid
selected = right - 1
if selected >= 0:
return self.history[index][selected][1]
return 0
Python-标准库
class SnapshotArray:
def __init__(self, length: int):
self.snap_id = 0
self.history = defaultdict(list)
def set(self, index: int, val: int) -> None:
self.history[index].append((self.snap_id, val))
def snap(self) -> int:
snap_id = self.snap_id
self.snap_id += 1
return snap_id
def get(self, index: int, snap_id: int) -> int:
# 找快照编号 <= snap_id 的最后一次修改记录
# 等价于找快照编号 >= snap_id+1 的第一个修改记录，它的上一个就是答案
j = bisect_left(self.history[index], (snap_id+1,)) - 1
if j >= 0:
return self.history[index][j][1]
return 0