LeetCode每日一题 ---- 1146.快照数组

LeetCode 每日一题 ---- 【1146.快照数组】

• 1146.快照数组
  • • 解法一：采用二分搜索法

快照数组问题解析

方法一：二分查找

首次尝试这种补充方法的题目时，当看到输入和输出用例时，感到有些困惑，这些输入和输出之间到底有什么联系呢？后来发现，输入用例实际上代表了方法调用的顺序以及调用的次数，本质上是传递给 main 方法的 arg 参数，并据此调用相应的函数。

简要说明题意，原题描述存在一定的模糊性。
SnapshotArray(int length)：这是一个初始化函数，其作用是创建用于存储快照的容器。
void set(index, val)：将指定索引 index 处的值设置为 val。
int snap()：生成一个快照，并记录该快照的编号以及其中包含的数据。
int get(index, snap_id)：根据提供的快照编号 snap_id 获取对应快照中索引为 index 的元素值。

如果直接按照题意进行模拟实现，则会面临两个主要问题：

1. 内存使用超出限制
2. 运行时间超出限制

针对上述问题的解决方案如下：

1. 内存超限的原因在于每次执行 snap 方法时都会生成一个新的快照。若直接复制整个数组内容，则随着操作次数增加，内存消耗会急剧上