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

1146.快照数组

方法一：二分查找

第一次做到这种补充方法的题目，然后看到输入和输出用例的时候，愣了一下，这输入和输出用例有啥关联啊？？后面发现，输入用例其实就是方法的调用顺序和调用次数，其实底层内部就是传给 main 方法的 arg 参数，然后调用对应的方法。

简单说一下题意，题目描述有点不清楚
SnapshotArray(int length)：就是初始化方法，初始化的容器其实就是保存快照的容器。
void set(index, val)：将指定位置 index，设置为指定值 val。
int snap()：生成一个快照，保存快照的 id，和快照内的元素。
int get(index, snap_id)：根据快照 id 获取指定快照中下标 index 的元素。

这道题目直接模拟的话会出现两个问题：

1. 超出内存限制
2. 超出时间限制

解决办法：

1. 超出内存限制是因为，每调用一次 snap 方法，就会生成一个快照，如果是直接将之前的数组复制一份的话，次数多了肯定会超限，而且如果我们只改变了一个元素的话，这样明显的很浪费空间的。所以我们只需记录一下修改的值以及对应的是在哪个快照下就可以了。
2. 超出时间限制是因为，如果我们遍历查找，其实这道题目有一个隐藏的点，快照的 id 是严格递增的，看到这句话就知道怎么优化了吧，二分！！！

class SnapshotArray {
    
    private int snap_cnt;
    private List<int[]>[] data;

    public SnapshotArray(int length) {
        snap_cnt = 0;
        data = new List[length];
        for (int i = 0; i < length; i ++ ) {
            data[i] = new ArrayList<int[]>();
        }
    }
    
    public void set(int index, int val) {
        data[index].add(new int[]{snap_cnt, val});
    }
    
    public int snap() {
        return snap_cnt ++ ;
    }
    
    public int get(int index, int snap_id) {
        int  x = binarySearch(index, snap_id);
        return x == 0 ? 0 : data[index].get(x - 1)[1];
    }

    private int binarySearch(int index, int snap_id) {
        int low = 0, high = data[index].size();
        while (low < high) {
            // 防止越界
            int mid = low + (high - low) / 2;
            int[] pair = data[index].get(mid);
            if (pair[0] > snap_id + 1 || (pair[0] == snap_id + 1 && pair[1] >= 0)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

/**
 * 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);
 */

 // ["SnapshotArray","set","snap","set","get"] 输入用例代表的是方法的执行顺序和执行次数

时间复杂度：
主要的时间复杂度就是二分的时间复杂度O(logn)

空间复杂度：
O(n)