The shapshot array is a data structure that supports the following operations:
nums = [0, 0, 0, 0, 0]
| | |
set 1 3 5
| | |
[1, 3, 5, 0, 0]
| | [1, 3, 5, 0, 0] // snapshot 0
| |
set 7 8
| |
[7, 3, 8, 0, 0]
[1, 3, 7, 8, 0] // snapshot 1
// No update
[1, 3, 7, 8, 0] // snapshot 2
| |
set 9 2
| |
[9, 3, 8, 2, 0]
[9, 3, 8, 2, 0] // snapshot 3There are some possible scenarios:
- We can have lots of
set()at the same index, then (very few)snapshot():
0 -> set(1) -> set(3) -> set(5) -> snapshot 0
|
get(snapId=0) = 5- We can have lots of
set()at the same index, but nosnapshot():
0 -> set(1) -> set(3) -> set(5) -> set(7)
// No get() operation since we didn't take any snapshot- We can snap multiple times without changing the array:
0 -> set(1) -> snapshot 0 -> snapshot 1 -> snapshot 2
| | |
get(snapId=0) = 1 | |
get(snapId=1) = 1 |
get(snapId=2) = 1
- 我们需要考虑一个效率的问题。我们每调用一次
snap()是否需要给每个元素都新建一次快照呢？显然如果大多数元素都没有更新过的话，再添加一次快照的效率不高。所以我们可以设置一个changed的集合，里面只存放上一次snap()之后变动过的元素，也就是被set()过的元素。 我们会发现对于每个元素而言，它被记录的snapId并不是连续的。所以我们应该在snaps[index]里面找到最后一个小于等于snapId的那个时间戳。- 如果有多個
set() = A, set() = B, set() = C但是只有一次snap()，那麼get()只會取得C；然而，如果我們只有一次set() = A，但是有多次snap()，那麼所有snap()值都會是A。也就是說我們只需要記錄「改動搭配snapId」的紀錄。
We just save all snapshots. It wastes memory if we have a large array but only a few elements are modified.
class SnapshotArray(private val length: Int) {
private var snapId = 0
private val array = IntArray(length)
private val snapshot = mutableListOf<IntArray>()
fun set(index: Int, `val`: Int) {
array[index] = `val`
}
fun snap(): Int {
snapshot.add(array.clone())
return snapId++
}
fun get(index: Int, snapId: Int): Int {
return snapshot[snapId][index]
}
}Since we might take multiple snapshots, but only retrieve the value at a specific snapshot, we need an efficient way to store and retrieve the value at a specific snapshot.
Instead of storing all values at every snapshot, we store only when a value is modified and we take a snapshot. We can use a list to store the modification records, which maintains a history of (snapId, value) pairs for each element in order in the array, and we only record the modified elements when set() is called.
// For nums[0]
0 -> set(1) -> snapshot 0 -> set(7) -> snapshot 1 -> ...... -> snapshot 2 -> set(9) -> snapshot 3
0 --------------------> 1 --------------------------------------------> 7 --------------------> 9
^ ^ ^ ^
record(snapId=0, 1) record(snapId=1, 7) X record(snapId=3, 9)
// Add modification records for nums[0]
record(snapId=0, 1) // set(1)
record(snapId=1, 7) // set(7)
record(snapId=3, 9) // set(9)
// The corresponding get() for nums[0] at different snapshots
get(snapId=0) = 1
get(snapId=1) = 7
get(snapId=2) = 7 // No update, we return the last value = 7 which is from the most latest record: snapId=1
get(snapId=3) = 9And since shapshot ID are incremental, so all modification records are sorted by snapId. When we call get(), we can binary search the snapshot to find the most recent records, which is the last snapshot <= snapId.
0 -> set(1) -> set(7) -> set(9) -> -> set(5) ->
\_ snapshot 0 \_ snapshot 1
get(snapId=0) = 9 get(snapId=1) = 5There are two edge cases to consider:
- Lot of
set()but only a few snapshot. - Few
set()but lots of snapshot.
data class Item(
val snapId: Int,
val value: Int
)
class SnapshotArray(private val length: Int) {
private var snapId = 0
// Space Complexity is `O(n + k)` where `n` is the length of the array and `k` is the number of modifications.
private val modificationRecords = Array<MutableList<Item>>(length) { mutableListOf() }
// Time Complexity is `O(1)`
fun set(index: Int, `val`: Int) {
// (Optional) We only record the modification if the value is really changed.
if (modificationRecords[index].lastOrNull()?.value == `val`) return
modificationRecords[index].add(Item(snapId, `val`))
}
// Time Complexity is `O(1)`
fun snap(): Int {
return snapId++
}
// Time Complexity is `O(log(k))` where `k` is the number of modifications.
fun get(index: Int, snapId: Int): Int {
return binarySearch(modificationRecords[index], snapId)
}
// We binary search the last element <= `snapId`
private fun binarySearch(records: List<Item>, snapId: Int): Int {
var left = 0
var right = records.size - 1
while (left <= right) {
val middle = left + (right - left) / 2
if (records[middle].snapId <= snapId) {
left = middle + 1
} else if (records[middle].snapId > snapId) {
right = middle - 1
}
}
// We need to check if not found, we return 0
return if (right in 0 until records.size) records[right].value else 0
}
}Or equivalently, we can use a TreeMap to store the modification records.
class SnapshotArray(val length: Int) {
private var snapId = 0
private val array = Array(length) { TreeMap<Int, Int>() }
fun set(index: Int, `val`: Int) {
array[index][snapId] = `val`
}
fun snap(): Int {
return snapId++
}
fun get(index: Int, snap_id: Int): Int {
val map = array[index] ?: return 0
val key = map.floorKey(snap_id)
return if (key != null) map[key]!! else 0
}
}