GuilinDev

Lc1146

05 August 2008

1146 Snapshot Array

原题

实现支持下列接口的「快照数组」- 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 的值。

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:

1
2
3
4
5
6
7
8
9

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 set, snap, and get.
  • 0 <= index < length`
  • 0 <= snap_id < (the total number of times we call snap()`)
  • 0 <= val <= 10^9`

分析

1）利用treemap记录snapid对应的list中保存此snapid的索引

2）List<Map<Integer,Integer>>，题意是要构建一个带有不同版本信息的数组，一种方法是每个版本都保存一个数组，但是这样显然产生了太多的冗余 只需要记录每个版本之间有区别的值即可

代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71

class SnapshotArray {

    Node[] arr;
    int snapTimes;

    public SnapshotArray(int length) {
        this.arr = new Node[length];
        this.snapTimes = 0;
        for(int i = 0; i < length; ++i) 
            arr[i] = new Node(0);
    }
    
    public void set(int index, int val) {
        Node cur = arr[index];
        if(cur.snapId == snapTimes) {
            cur.val = val;
            cur.vals.set(cur.idx, val);
        } else {
            cur.val = val;
            cur.vals.add(val);
            cur.idx++;
            cur.snapId = snapTimes;
            cur.map.put(snapTimes, cur.idx);
        }
        return;
    }
    
    public int snap() {
        snapTimes++;
        return snapTimes - 1;
    }
    
    public int get(int index, int snap_id) {
        Node cur = arr[index];
        if(cur.map.containsKey(snap_id)) {
            int idx = cur.map.get(snap_id);
            return cur.vals.get(idx);
        } else {
            int key = cur.map.lowerKey(snap_id);
            return cur.vals.get(cur.map.get(key));
        }
    }
}

class Node {
    int val;
    int idx;
    int snapId;
    List<Integer> vals;
    TreeMap<Integer, Integer> map;

    Node(int v) {
        this.val = v;
        this.vals = new ArrayList();
        this.idx = 0;
        this.snapId = 0;
        this.map = new TreeMap();
        vals.add(v);
        
        map.put(0, idx);
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */


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

class SnapshotArray {
    
    //list.get(index)应为数组下标为index处的值
    //每一个Map记录的是当前下标位置的值的变动，<版本号，新值>
    private List<Map<Integer,Integer>> list;
    private int snapId;

    public SnapshotArray(int length) {
        list = new ArrayList<>();
        for(int i = 0; i < length; i++){
            list.add(new HashMap<Integer,Integer>());
        }
        snapId = 0;
    }
    
    public void set(int index, int val) {
        //在index处放入此次版本更新的值
        list.get(index).put(this.snapId,val);
    }
    
    public int snap() {
        return snapId++;
    }
    
    public int get(int index, int snap_id) {
        //寻找snap_id版本前，最后一次更新的值
        for(int i = snap_id; i >= 0; i--) {
            if (list.get(index).containsKey(snap_id)) {
                return list.get(index).get(snap_id);
            }
            --snap_id;
        }
        return 0;
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */
This site is open source. Improve this page.