1
2
3
4
5
6
7
8
9

输入：["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] = 5
snapshotArr.snap();  // 获取快照，返回 snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

// @lc code=start
use std::collections::BTreeMap;

/// ## 解题思路
/// - 数组+BTreeMap
struct SnapshotArray {
    data: Vec<BTreeMap<i32, i32>>,  // idx, snap_id -> val
    size: usize,  // data size
    snap_id: i32, // snap id
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl SnapshotArray {

    fn new(length: i32) -> Self {
        Self {
            size: length as usize,
            snap_id: 0,
            data: vec![BTreeMap::new(); length as usize],
        }
    }

    fn set(&mut self, index: i32, val: i32) {
        assert!(index < self.size as i32);

        self.data.get_mut(index as usize)
            .unwrap()
            .insert(self.snap_id, val);
    }

    fn snap(&mut self) -> i32 {
        self.snap_id += 1;
        self.snap_id - 1
    }

    fn get(&self, index: i32, snap_id: i32) -> i32 {
        assert!(snap_id <= self.snap_id);

        *self.data.get(index as usize)
            .unwrap()
            .range(..=snap_id)
            .last()
            .unwrap_or((&0, &0))
            .1
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * let obj = SnapshotArray::new(length);
 * obj.set(index, val);
 * let ret_2: i32 = obj.snap();
 * let ret_3: i32 = obj.get(index, snap_id);
 */
// @lc code=end