思路：初始时，使用的思路是对于每个快照的数组都进行一次副本保存，但是提交后是时间超出。因此基于 灵神. - 力扣（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;elseright = 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);*/