2024年4月26日力扣每日一题（1146）
前言
这道题在做的时候感觉很简单，题意很容易理解，但直接去做直接干爆内存，参考了一下灵神的代码，豁然开朗，觉得这道题很有意思，便想着写篇博客记录一下，自己在算法上的欠缺还很多，如有不足或错误之处还望见谅。
1.快照数组
QQ截图20240427143216.png
首先阅读一下题目，题目要求我们实现一个接口，每调用一次get方法，会更新一下索引index的数据，每调用一次get方法，会返回根据snap_id的数据来返回index的历史数据。
2.思路
看到这道题，我首先想到的就是暴力计算，不停的复制数组，但这种方法，大概率不会通过，不是超时就是爆内存，在最坏的情况下，这道题需要复制50000次长度为50000的数组，这会超出内存限制，这让我头大，没了思路，想到map集合可以根据键值对存储数据，似乎可以用map来实现，但具体该怎么使用，自己没有一个思路，这时候去看了题解，瞻仰了一下[灵神的代码题解](https://leetcode.cn/problems/snapshot-array/solutions/2756291/ji-lu-xiu-gai-li-shi-ha-xi-biao-er-fen-c-b1sh)，感觉豁然开朗，大佬就是大佬，太强了。
3.灵神的代码
class SnapshotArray {
// 当前快照编号，初始值为 0
private int curSnapId;
// 每个 index 的历史修改记录
private final Map<Integer, List<int[]>> history = new HashMap<>();
public SnapshotArray(int length) {
}
public void set(int index, int val) {
history.computeIfAbsent(index, k -> new ArrayList<>()).add(new int[]{curSnapId, val});
}
public int snap() {
return curSnapId++;
}
public int get(int index, int snapId) {
if (!history.containsKey(index)) {
return 0;
}
List<int[]> h = history.get(index);
int j = search(h, snapId);
return j < 0 ? 0 : h.get(j)[1];
}
// 返回最大的下标 i，满足 h[i][0] <= x
// 如果不存在则返回 -1
private int search(List<int[]> h, int x) {
// 开区间 (left, right)
int left = -1;
int right = h.size();
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// h[left][0] <= x
// h[right][1] > x
int mid = left + (right - left) / 2;
if (h.get(mid)[0] <= x) {
left = mid; // 区间缩小为 (mid, right)
} else {
right = mid; // 区间缩小为 (left, mid)
}
}
// 根据循环不变量，此时 h[left][0] <= x 且 h[left+1][0] = h[right][0] > x
// 所以 left 是最大的满足 h[left][0] <= x 的下标
// 如果不存在，则 left 为其初始值 -1
return left;
}
}
作者：灵茶山艾府
链接：https://leetcode.cn/problems/snapshot-array/solutions/2756291/ji-lu-xiu-gai-li-shi-ha-xi-biao-er-fen-c-b1sh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
4.自己对这道题的理解
1.computeIfAbsent方法
在看灵神代码时出现了一个陌生的API，看来自己的知识欠缺还比较多，去查了一下这个API的使用方法，简单介绍一下。
computeIfAbsent 是 Java 8 引入的一个非常有用的 Map 接口方法，它允许你根据指定的键来条件性地计算并插入一个值。如果指定的键尚未与值关联（或者映射到 null），则它会使用提供的函数计算一个值，并将其与该键关联。
这是其基本用法：
Map<K, V> map = ...; // 假设你已经有了一个Map
V value = map.computeIfAbsent(key, k -> {
// 在这里，你可以根据键 k 来计算一个值
// 例如，你可能想从数据库或其他数据源获取数据
return computeValue(k);
});
在这个例子中，key 是你要检查的键，而 k -> computeValue(k) 是一个 Function，它根据键 k 来计算一个值。
- 如果
map中已经存在与key关联的值（即使该值为null），那么computeIfAbsent将返回该值，并且不会执行提供的函数。 - 如果
map中不存在与key关联的值，那么computeIfAbsent将执行提供的函数，使用其返回的值与key关联，并返回该值。
这个方法非常有用，因为它允许你以原子方式执行“如果键不存在则插入”的操作，而无需首先检查键是否存在。这可以简化代码，并减少并发环境中可能发生的竞态条件。
注意：computeIfAbsent 不会替换已经存在的值（即使该值为 null）。如果你需要替换已经存在的值（包括 null），你应该使用 compute 或 merge 方法。
那么在灵神的代码中
public void set(int index, int val) {
history.computeIfAbsent(index, k -> new ArrayList<>()).add(new int[]{curSnapId, val});
}
这段代码的意思是，如果键k，没有对应的值，那就新建一个列表，并且在这个列表中，添加一个数组，这个数组的数据包含两个值，一个是当前的快照编号，另一个是当前要设置的值。
2.解题思路
根据灵神的解题思路，每次修改之后，不再重复去复制数组，而是单纯再后面添加一个元素，并且由于每次修改后添加的数据是有序的，在调用get方法时，我们可以使用二分查找来查找相对应的历史版本。
二分查找
这道题的二分查找也是一个比较值得注意的点，自己在写的时候，简单的二分查找难住了我不短的时间。
private int search(List<int[]> l, int x) {
int left = 0;
int right = l.size() - 1;
int result = -1; // 初始化result为-1，表示尚未找到匹配项
while (left <= right) {
int mid = left + (right - left) / 2;
if (l.get(mid)[0] <= x) {
// 如果中间位置的快照ID小于等于x，更新result并继续在右侧搜索，以找到可能的更大快照ID
result = mid;
left = mid + 1;
} else {
// 如果中间位置的快照ID大于x，则在左侧继续搜索
right = mid - 1;
}
}
// 返回不大于x的最大快照ID的索引，如果没有找到则返回-1
return result;
}