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
| type SnapshotArray struct {
version int
data [][][]int
}
func Constructor(length int) SnapshotArray {
return SnapshotArray{
version: 0,
data: make([][][]int, length),
}
}
func (this *SnapshotArray) Set(index int, val int) {
this.data[index] = append(this.data[index], []int{this.version, val})
}
func (this *SnapshotArray) Snap() int {
oldVersion := this.version
this.version++
return oldVersion
}
func (this *SnapshotArray) Get(index int, snap_id int) int {
return binarySearch(this.data[index], snap_id)
}
func binarySearch(arr [][]int, version int) int {
if len(arr) == 0 {
return 0
}
left := 0
right := len(arr) - 1
for left < right {
mid := ((right - left + 1) >> 1) + left
if arr[mid][0] > version {
right = mid - 1
} else {
left = mid
}
}
if arr[left][0] <= version {
return arr[left][1]
}
return 0
}
/**
* Your SnapshotArray object will be instantiated and called as such:
* obj := Constructor(length);
* obj.Set(index,val);
* param_2 := obj.Snap();
* param_3 := obj.Get(index,snap_id);
*/
|
