题目

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

示例：

1
2
3
4
5
6
7
8
9
输入：["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

题解

题目描述有点绕。举个例子：set是写入数组，snap是保存数组到快照里，get是从快照里拿历史数组取里面的值。每次操作时数据如下
new SnapshotArray(3)时 数组[0,0,0], 快照数组[]
snapshotArr.set(0,5) 数组[5,0,0], 快照数组[]
snapshotArr.snap() 数组[5,0,0], 快照数组[[5,0,0]]
snapshotArr.set(0,6) 数组[6,0,0], 快照数组[[5,0,0]]
snapshotArr.get(0,0) 数组[6,0,0], 快照数组[[5,0,0]]。get(0,0)取快照数组里第0个数组的第0个元素
方法一：模拟
根据上面模拟出操作流程，但是最后数据大会超时，用例68/75通过，得优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class SnapshotArray:

    def __init__(self, length: int):
        self.snap_array = []
        self.array = [0] * length

    def set(self, index: int, val: int) -> None:
        self.array[index] = val

    def snap(self) -> int:
        self.snap_array.append(deepcopy(self.array))
        return len(self.snap_array) - 1

    def get(self, index: int, snap_id: int) -> int:
        return self.snap_array[snap_id][index]

方法二：哈希+二分法
思考：
暴力模拟方法会超时
每次修改数组的一个元素都重新复制一个数组，是不是太浪费？数组最长5000，最坏情况就是修改长度为5000的数组的一个元素，然后复制。
有没有可能只记录修改记录，而不是复制整个数组
换个视角，调用 set(index,val) 时，不去修改数组，而是往 index的历史修改记录末尾添加一条数据：此时的快照编号和 val。
思路：
维护一个history哈希表记录数组的每一个元素的变更历史。哈希key是表示数组的第几个元素，哈希value是列表，列表每个元素记录快照id和对应的变更值
例如：history = {1:[(1,2),(2,4)]}表示数组的第1个元素在快照1时值为2，在快照2时值为4。

  • set时就往对应的列表里添加一条新的变更记录
  • snap时就把快照id增加1
  • get时，因为snap的快照id是递增的，所以可以使用二分法快速从快照变更列表里找到某快照id时变更的值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class SnapshotArray:
        def __init__(self, _: int):
            self.cur_snap_id = 0
            self.history = defaultdict(list)  # 每个 index 的历史修改记录

        def set(self, index: int, val: int) -> None:
            self.history[index].append((self.cur_snap_id, val))

        def snap(self) -> int:
            self.cur_snap_id += 1
            return self.cur_snap_id - 1

        def get(self, index: int, snap_id: int) -> int:
            # 找快照编号 <= snap_id 的最后一次修改记录
            # 等价于找快照编号 >= snap_id+1 的第一个修改记录，它的上一个就是答案
            j = bisect_left(self.history[index], (snap_id + 1,)) - 1
            return self.history[index][j][1] if j >= 0 else 0