1146. 快照数组

题目

实现支持下列接口的「快照数组」- 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 < length

0 <= 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