力扣1146 快照数组

思路：初始时，使用的思路是对于每个快照的数组都进行一次副本保存，但是提交后是时间超出。因此基于 灵神. - 力扣（LeetCode） 的思路不构建数组，而是保存每个数组位置set的记录，记录采用的是键值对的形式，键为当前快照号，值为传递过来需要修改的val；这样构造函数、set以及snap方法都可以比较精简的得到解决。

对于get方法，若没有构建数组存储每个时刻的数据而是直接记录版本更新情况的话，在二分查找时所检索的不是等于当前snap_id的记录，而是需要找到索引list中小于snap_id的第一个元素（因为同一个index出，可以有多个快照号相同的记录）；因此二分查找使用红蓝染色法，返回left。

class SnapshotArray {
    // 快照编号
    int snapidx;
    Map<Integer, List<int[]>> map = new HashMap<>();

    public SnapshotArray(int length) {
        // 定位快照编号
        snapidx = 0;
        // arr = new int[length];
        // 构建map，提前为每个索引建立好历史记录列表
        for(int i=0; i<length; i++){
            List<int[]> list = new ArrayList<>();
            map.put(i, list);
        }
    }
    
    public void set(int index, int val) {
        // 当前版本的数据更新
        // arr[index] = val;
        // 增加一条记录
        List<int[]> list = map.get(index);
        list.add(new int[]{snapidx, val});  // list内加入的元素总是按照时间的先后往其中加入的
        map.put(index, list);
    }
    
    public int snap() {
        snapidx++;
        return snapidx-1;
    }
    
    public int get(int index, int snap_id) {
        // 获取到当前的索引位置的历史版本
        List<int[]> list = map.get(index);
        // 本质上可以通过遍历来实现，使用二分查找加快查找的速度
        int idx = binarysearch(list, snap_id);
        return idx<0? 0:list.get(idx)[1];
    }

    public int binarysearch(List<int[]> list, int snapid){
        // 红蓝染色法的二分查找
        int left = -1;
        int right = list.size();
        while(left + 1 != right){
            int mid = left + (right-left)/2;
            if(list.get(mid)[0] <= snapid)
                left = mid;
            else
                right = mid;
        }

        return left;

    }
}

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