LeetCode 题解工作台
快照数组
实现支持下列接口的「快照数组」- SnapshotArray： SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。 初始时，每个元素都等于 0 。 void set(index, val) - 会将指定索引 index 处的元素设置为 val 。…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们维护一个长度为 的数组，数组中的每个元素是一个列表，用来存储每次设置的值以及对应的快照 ID。 调用 `set` 方法时，将值和快照 ID 添加到对应索引的列表中。时间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
实现支持下列接口的「快照数组」- SnapshotArray：
SnapshotArray(int length)- 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。void set(index, val)- 会将指定索引index处的元素设置为val。int snap()- 获取该数组的快照，并返回快照的编号snap_id（快照号是调用snap()的总次数减去1）。int get(index, snap_id)- 根据指定的snap_id选择快照，并返回该快照指定索引index的值。
示例：
输入：["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
输出：[null,null,0,null,5]
解释：
SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
snapshotArr.set(0,5); // 令 array[0] = 5
snapshotArr.snap(); // 获取快照，返回 snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0); // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5
提示：
1 <= length <= 50000- 题目最多进行
50000次set，snap，和get的调用 。 0 <= index < length0 <= snap_id <我们调用snap()的总次数0 <= val <= 10^9
解题思路
方法一：数组 + 二分查找
我们维护一个长度为 的数组，数组中的每个元素是一个列表，用来存储每次设置的值以及对应的快照 ID。
调用 set 方法时，将值和快照 ID 添加到对应索引的列表中。时间复杂度 。
调用 snap 方法时，我们先将快照 ID 加一，然后返回快照 ID 减一。时间复杂度 。
调用 get 方法时，我们使用二分查找找到对应位置的第一个快照 ID 大于 snap_id 的值，然后返回前一个的值。如果找不到，则返回 0。时间复杂度 。
空间复杂度 。
class SnapshotArray:
def __init__(self, length: int):
self.arr = [[] for _ in range(length)]
self.i = 0
def set(self, index: int, val: int) -> None:
self.arr[index].append((self.i, val))
def snap(self) -> int:
self.i += 1
return self.i - 1
def get(self, index: int, snap_id: int) -> int:
i = bisect_left(self.arr[index], (snap_id, inf)) - 1
return 0 if i < 0 else self.arr[index][i][1]
# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n \log n + k), where n is the number of set operations and k is the number of get queries, due to binary search per get. Space complexity is O(n + k) because we only store modified elements per snap rather than full array copies. |
| 空间 | O(n + k) |
面试官常问的追问
外企场景- question_mark
Expectations that each index maintains its own change history to avoid O(n) scanning.
- question_mark
Focus on using binary search to optimize get operations over historical snapshots.
- question_mark
Discussion on trade-offs between memory usage and snapshot speed is important.
常见陷阱
外企场景- error
Storing full arrays on each snap causes memory overflow for large inputs.
- error
Using linear search in get leads to TLE for many operations.
- error
Forgetting to append initial value (e.g., 0) for all indices before the first snap can produce incorrect results.
进阶变体
外企场景- arrow_right_alt
SnapshotArray with range updates instead of single index updates.
- arrow_right_alt
Persistent segment tree approach to maintain snapshot history for large arrays.
- arrow_right_alt
Tracking multiple attributes per index, requiring nested versioned lists.