题目 #
实现支持下列接口的「快照数组」- 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
解法 #
- Tag：Binary Search
针对每次快照，我们没有必要进行全量保存，而只进行差异保存。 也就是说，当我们进行快照拍摄时，我们仅针对相对于上次快照产生了变化的元素保存一次快照值。 即每一个元素分别保存自己的快照列表，且仅保存发生过变化的快照。 当我们获取某元素的在某时间的快照值时，我们通过二分法查找到该快照 id 的对应值，若该 id 不在列表中，则说明该次快照并没有值变化，我们取最后一个小于该 id 的快照值。
代码 #
def bs(arr, target, left, right):
if right < left:
return right
mid = (left + right) // 2
if arr[mid] > target:
return bs(arr, target, left, mid - 1)
else:
return bs(arr, target, mid + 1, right)
class SnapshotArray:
def __init__(self, length: int):
self.snapId = -1
self.changed = set()
self.arr = [{-1: 0} for _ in range(length)]
def set(self, index: int, val: int) -> None:
self.changed.add(index)
self.arr[index][-1] = val
def snap(self) -> int:
self.snapId += 1
for index in self.changed:
self.arr[index][self.snapId] = self.arr[index][-1]
self.changed.clear()
return self.snapId
def get(self, index: int, snap_id: int) -> int:
ids = list(self.arr[index].keys())
idx = bs(ids, snap_id, 0, len(ids) - 1)
if idx >= 0 and ids[idx] >= 0 and ids[idx] in self.arr[index]:
return self.arr[index][ids[idx]]
else:
return 0