1146.快照数组

链接：1146.快照数组
难度：Medium
标签：设计、数组、哈希表、二分查找
简介：实现支持下列接口的「快照数组」- SnapshotArray。

题解 1 - python

• 编辑时间：2024-04-26
• 执行用时：424ms
• 内存消耗：42.39MB
• 编程语言：python
• 解法介绍：仅存储变更。

class SnapshotArray:
    def __init__(self, length: int):
        self.next_snap = 0
        self.list = [[(-1, 0)] for _ in range(length)]
    def set(self, index: int, val: int) -> None:
        if self.list[index][-1][0] == self.next_snap:
            self.list[index][-1] = (self.next_snap, val)
        else:
            self.list[index].append((self.next_snap, val))
    def snap(self) -> int:
        snap = self.next_snap
        self.next_snap += 1
        return snap
    def get(self, index: int, snap_id: int) -> int:
        res = bisect_right(self.list[index], (snap_id, 1e10))
        return self.list[index][res - 1][1]