1146. Snapshot Array

Implement a SnapshotArray that supports the following interface:

  • SnapshotArray(int length) initializes an array-like data structure with the given length.  Initially, each element equals 0.
  • void set(index, val) sets the element at the given index to be equal to val.
  • int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
  • int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Example 1:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation:
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

Constraints:

  • 1 <= length <= 50000
  • At most 50000 calls will be made to setsnap, and get.
  • 0 <= index < length
  • 0 <= snap_id < (the total number of times we call snap())
  • 0 <= val <= 10^9

这道题让实现一个 SnapshotArray 的类,具有给数组拍照的功能,就是说在某个时间点 spapId 拍照后,当前数组的值需要都记录下来,同理,每一次调用 snap() 函数时,都需要记录整个数组的状态,这是为了之后可以查询任意一个时间点上的任意一个位置上的值。最简单粗暴的方法当前就是用一个二维数组,每次拍照的时候,都把整个数组都存到二维数组中,其坐标就是 snapId。但是这种方法不高效,而且占用了巨大的空间,被 OJ 豪不留情的抹杀掉了。来分析一下不高效的原因,这是因为每次拍照时,可能数组的大部分数据并没有变动,每次都再存一遍整个数组是浪费的。这里我们关心的是调用 set() 函数,因为这会改变数组的值,若能建立 snapId 和更新值之间的映射,就可以根据二分法来快速定位某一个 snapId 的值了,因为 snapId 是按顺序递增的。这样就可以用一个 Vector of Map 或者 Map of Map 的数据结构来实现,外层的 TreeMap 是映射建立数组坐标到内层 TreeMap 之间的映射,内层的 TreeMap 是建立 snapId 和更新值之间的映射。初始化时,要将 0->0 这个映射对儿加到每一个位置,因为初始化时数组的每个元素都是0。在 set() 函数中就可以更新 HashMap 中的映射值,snap() 就直接累加 snapId,比较麻烦的就是 get() 函数,给定的 snapId 可能在内层的 HashMap 中不存在,需要查找第一个不大于给定 snapId 的映射值,那么就先找第一个大于 snapId 的位置,再回退一位就好了,参见代码如下:

class SnapshotArray {
public:
    SnapshotArray(int length) {
        for (int i = 0; i < length; ++i) {
            snapMap[i] = {{0, 0}};
        }
    }
    
    void set(int index, int val) {
        snapMap[index][snapId] = val;
    }
    
    int snap() {
        return snapId++;
    }
    
    int get(int index, int snap_id) {
        auto it = snapMap[index].upper_bound(snap_id);
        --it;
        return it->second;
    }

private:
    int snapId = 0;
    map<int, map<int, int>> snapMap;
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1146

参考资料:

https://leetcode.com/problems/snapshot-array/

https://leetcode.com/problems/snapshot-array/discuss/350562/JavaPython-Binary-Search

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation