★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（）

➤GitHub地址：

➤原文地址： 

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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 3snapshotArr.set(0,5);  // Set array[0] = 5snapshotArr.snap();  // Take a snapshot, return snap_id = 0snapshotArr.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 set, snap, and get.
• 0 <= index < length
• 0 <= snap_id < (the total number of times we call snap())
• 0 <= val <= 10^9

---

实现支持下列接口的「快照数组」- SnapshotArray：

• SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
• void set(index, val) - 会将指定索引 index 处的元素设置为 val。
• int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
• int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。

示例：

输入：["SnapshotArray","set","snap","set","get"]     [[3],[0,5],[],[0,6],[0,0]]输出：[null,null,0,null,5]解释：SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组snapshotArr.set(0,5);  // 令 array[0] = 5snapshotArr.snap();  // 获取快照，返回 snap_id = 0snapshotArr.set(0,6);snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5

提示：

• 1 <= length <= 50000
• 题目最多进行50000 次set，snap，和 get的调用 。
• 0 <= index < length
• 0 <= snap_id < 我们调用 snap() 的总次数
• 0 <= val <= 10^9

---

480ms

1 class SnapshotArray { 2  3     private var dict = [Int: Int]() 4     private var snapshots = [[Int: Int]]() 5      6     init(_ length: Int) { 7         //array = Array(repeating: 0, count: length + 1) 8     } 9     10     func set(_ index: Int, _ val: Int) {11         dict[index] = val12     }13     14     func snap() -> Int {15         snapshots.append(dict)16         return snapshots.count - 117     }18     19     func get(_ index: Int, _ snap_id: Int) -> Int {20         return snapshots[snap_id][index] ?? 021     }22 }23 24 /**25  * Your SnapshotArray object will be instantiated and called as such:26  * let obj = SnapshotArray(length)27  * obj.set(index, val)28  * let ret_2: Int = obj.snap()29  * let ret_3: Int = obj.get(index, snap_id)30  */

---

Runtime: 828 ms

Memory Usage: 27.8 MB

1 class SnapshotArray { 2     var vv:[[Int:Int]] = [[Int:Int]]() 3  4     init(_ length: Int) { 5         vv.append([Int:Int]())         6     } 7      8     func set(_ index: Int, _ val: Int) { 9         vv[vv.count - 1][index] = val10     }11     12     func snap() -> Int {13         vv.append([Int:Int]()) 14         return vv.count - 215     }16     17     func get(_ index: Int, _ snap_id: Int) -> Int {18         for i in stride(from:snap_id,through:0,by:-1)19         {20             if vv[i][index] != nil21             {22                 return vv[i][index]!23             }24         }25         return 026     }27 }28 29 /**30  * Your SnapshotArray object will be instantiated and called as such:31  * let obj = SnapshotArray(length)32  * obj.set(index, val)33  * let ret_2: Int = obj.snap()34  * let ret_3: Int = obj.get(index, snap_id)35  */