本文主要是介绍2024年4月26日力扣每日一题（1146），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2024年4月26日力扣每日一题（1146）
前言
这道题在做的时候感觉很简单，题意很容易理解，但直接去做直接干爆内存，参考了一下灵神的代码，豁然开朗，觉得这道题很有意思，便想着写篇博客记录一下，自己在算法上的欠缺还很多，如有不足或错误之处还望见谅。
1.快照数组
首先阅读一下题目，题目要求我们实现一个接口，每调用一次get方法，会更新一下索引index的数据，每调用一次get方法，会返回根据snap_id的数据来返回index的历史数据。
2.思路
看到这道题，我首先想到的就是暴力计算，不停的复制数组，但这种方法，大概率不会通过，不是超时就是爆内存，在最坏的情况下，这道题需要复制50000次长度为50000的数组，这会超出内存限制，这让我头大，没了思路，想到map集合可以根据键值对存储数据，似乎可以用map来实现，但具体该怎么使用，自己没有一个思路，这时候去看了题解，瞻仰了一下灵神的代码题解，感觉豁然开朗，大佬就是大佬，太强了。
3.灵神的代码
class SnapshotArray {// 当前快照编号，初始值为 0private 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// 如果不存在则返回 -1private 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] > xint 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 为其初始值 -1return 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;
}
这篇关于2024年4月26日力扣每日一题（1146）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
