2024年4月26日力扣每日一题（1146）

2024年4月26日力扣每日一题（1146）

前言

​ 这道题在做的时候感觉很简单，题意很容易理解，但直接去做直接干爆内存，参考了一下灵神的代码，豁然开朗，觉得这道题很有意思，便想着写篇博客记录一下，自己在算法上的欠缺还很多，如有不足或错误之处还望见谅。

1.快照数组

​ 首先阅读一下题目，题目要求我们实现一个接口，每调用一次get方法，会更新一下索引index的数据，每调用一次get方法，会返回根据snap_id的数据来返回index的历史数据。

2.思路

​ 看到这道题，我首先想到的就是暴力计算，不停的复制数组，但这种方法，大概率不会通过，不是超时就是爆内存，在最坏的情况下，这道题需要复制50000次长度为50000的数组，这会超出内存限制，这让我头大，没了思路，想到map集合可以根据键值对存储数据，似乎可以用map来实现，但具体该怎么使用，自己没有一个思路，这时候去看了题解，瞻仰了一下灵神的代码题解，感觉豁然开朗，大佬就是大佬，太强了。

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;  
}