2024.4.26力扣每日一题—

2024.4.26力扣每日一题——快照数组

2024.4.26

- - 题目来源
  - 我的题解
  - - 方法一 TreeMap
    - 方法二哈希表+二分法

题目来源

力扣每日一题；题序：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 {
    // 当前快照编号，初始值为 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;
    }
}