2024.4.26
题目来源
我的题解
方法一 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(logq),其中 q 为 set 的调用次数。
空间复杂度:O(q)
class SnapshotArray {
// 当前快照编号,初始值为 0
private 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
// 如果不存在则返回 -1
private 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] > x
int 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 为其初始值 -1
return left;
}
}
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~