本文共 1720 字，大约阅读时间需要 5 分钟。

实现支持下列接口的「快照数组」- 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] = 5snapshotArr.snap();  // 获取快照，返回 snap_id = 0snapshotArr.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

解题思路

这个问题和之前的问题非常类似，所以我们可以采用之前的思想，将每次数据的变化按照[snap_id, val]的方式存储。

class SnapshotArray:    def __init__(self, n):        self.data = [[[-1, 0]] for _ in range(n)]        self.snap_id = 0    def set(self, index, val):        self.data[index].append([self.snap_id, val])    def snap(self):        self.snap_id += 1        return self.snap_id - 1    def get(self, index, snap_id):        i = bisect.bisect_right(self.data[index], [snap_id, float("inf")]) - 1        return self.data[index][i][1]

当然你可以通过字典将所有变化的数据存储起来

class SnapshotArray:    def __init__(self, length: int):        self.dif = {
   }        self.snaps = []    def set(self, index: int, val: int) -> None:        self.dif[index] = val    def snap(self) -> int:        self.snaps.append(self.dif.copy())        return len(self.snaps) - 1    def get(self, index: int, snap_id: int) -> int:        return self.snaps[snap_id][index] if index in self.snaps[snap_id] else 0

实际上这样做的效率更高。

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/98485378 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！