1146. 快照数组：利用二分查找加速操作记录的查询，进而降低快照的空间开销.md

题目简述：

实现支持下列接口的「快照数组」- 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 <= length <= 50000
• 题目最多进行50000 次set，snap，和 get的调用 。
• 0 <= index < length
• 0 <= snap_id < 我们调用 snap() 的总次数
• 0 <= val <= 10^9

题目链接：1146. 快照数组

思路

最初我打算真的保存每次快照的完整数组，正确性上没有问题，但实际的测试中会超出内存限制。

class SnapshotArray {

    private int id = -1;
    private int[] arr;
    private List<int[]> list;

    public SnapshotArray(int length) {
        arr = new int[length];
        list = new ArrayList<>();
    }
    
    public void set(int index, int val) {
        arr[index] = val;
    }
    
    public int snap() {
        id++;
        list.add(arr.clone());
        return id;
    }
    
    public int get(int index, int snap_id) {
        return list.get(snap_id)[index];
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */

在给定的数据范围下，我们并不能保存每次快照的完整数组。

于是想到缩小颗粒度，不再保存每次快照的完整数组，而只保存针对数组上各个位置上的确实有效的操作记录，记录包含 id 与更新后的值 val。

这样做是出于两点考虑：

1. get() 方法不要求返回整个数组的快照，只需要返回数组快照上某个索引位置上的值；
2. 我们不可能再只保存更少的信息，否则就会产生遗漏，导致我们可能永远也无法再找回某次快照中数组上某个位置上的值。

我们用 buckets 数组保存原数组中每个位置上的有效操作记录，操作记录分别对应 id 与 val，即更新后的值。比较好的方案是用两个 buckets 分别存 id 与 val，避免封装对象产生的开销。

这样，如果某个位置在一次快照中没有被更新，那么他就不会被记录。我们可以用二分查找快速定位上一次改动的快照 id，再通过 id 得到值。

代码

class SnapshotArray {

    private int id = -1;
    private int[] arr;
    private List<Integer>[] idBucket;
    private List<Integer>[] valBucket;

    public SnapshotArray(int length) {
        arr = new int[length];
        idBucket = (List<Integer>[]) new ArrayList[length];
        valBucket = (List<Integer>[]) new ArrayList[length];
        for (int i = 0; i < length; i++) {
            idBucket[i] = new ArrayList<>();
            idBucket[i].add(-1);
            valBucket[i] = new ArrayList<>();
            valBucket[i].add(0);
        }
    }
    
    public void set(int index, int val) {
        if (arr[index] != val) {
            arr[index] = val;
            idBucket[index].add(id + 1);
            valBucket[index].add(val);
        }
    }
    
    public int snap() {
        id++;
        return id;
    }
    
    public int get(int index, int snap_id) {
        List<Integer> ids = idBucket[index];
        snap_id++;  // let it be 1-based

        int l = 0;
        int r = ids.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (ids.get(mid) < snap_id) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return valBucket[index].get(r);
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */