题目来源

力扣每日一题；题序：1146

我的题解

方法一 TreeMap

使用TreeMap记录每个snip_id下的修改记录。
在set时，判断snip_id下是否有修改记录，若无则将最后一次有修改记录的snip_id下的修改记录复制给当前的snip_id，然后再添加新的修改记录。
在snap时只需要直接snip_id+1
在get时，从snip_id开始遍历，依次减1，找到最后一次index修改的记录。

时间复杂度：初始化、snap 均为 O(1)，set为O(logn)，get 为 O(h+k)，h是查找快照ID时需要遍历的层数（从snap_id到0），k是找到特定索引的值所需的映射查找次数。在最坏的情况下，如果每次快照都修改了该索引，那么k可以是等于快照数量的。但是，如果快照修改不是那么频繁，这个值会小得多。
空间复杂度：除了初始化基本都是O(1)

class SnapshotArray {TreeMap<Integer,Map<Integer,Integer>> map;int[] arr;int count;int len;public SnapshotArray(int length) {map=new TreeMap<>();arr=new int[length];count=0;len=length;map.put(0,new HashMap<>());}public void set(int index, int val) {if(!map.containsKey(count)&&count!=0)map.put(count,new HashMap<>(map.get(map.lastKey())));Map<Integer,Integer> change=map.get(count);change.put(index,val);map.put(count,change);}public int snap() {return count++;}public int get(int index, int snap_id) {int res=arr[index];for(int i=snap_id;i>=0;i--){if(map.containsKey(i)&&map.get(i).containsKey(index)){res=map.get(i).get(index);break;}}return res;}
}

方法二 哈希表+二分法

参照灵神的代码

时间复杂度：初始化、set、snap 均为 O(1)，get为 O(log⁡q)，其中 q 为 set 的调用次数。
空间复杂度：O(q)

class SnapshotArray {// 当前快照编号，初始值为 0private 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// 如果不存在则返回 -1private 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] > xint 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 为其初始值 -1return left;}
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~