KK's blog

每天积累多一些

0%

LeetCode 1146 Snapshot Array

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>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</pre>

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

</div>

题目大意：

设计一个数据结构支持数组的快照

Binary Search解题思路(推荐)：

暴力法是每次快照时候，将当时的数组的所有值存入dict中，key为(snap_id, index), value为数组值，得到MLE 后来考虑用二分法优化snap，将数值跟前值不同才存入历史记录，但得到TLE，应该是因为snap时间太长，因为要遍历整个数组
所以应该将存入历史这一步放在set中，每次值改变才存入历史记录，虽然一个snap_id可能会存入多值，大部分是不需要，因为同一个snap_id应该取最新值，但这样设计费了空间，省了时间。

解题步骤：

N/A

注意事项：

  1. 历史记录为3d数组，第一维为数组index, 第二维为所有历史记录，第三维为每一个记录为[snap_id, value]。由于数组初始值为0，所以初始历史记录为[-1, 0]
  2. snap_id和题目要求的id差1，比如第一次call snap为0，但是之前的snap应该为-1
  3. 最容易错的在于二分法，要先将snap_id + 1，比如[-1, 0], [0, 5], [0, 6], [0, 2], [1, 1], [1, 4]...找snap_id = 0的值也就是要找最后的，所以先加1，找到[1, 1]再下标减1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class SnapshotArray(TestCases):

    def __init__(self, length: int):
        self.snap_id = 0
        self.history = [[[-1, 0]] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        self.history[index].append([self.snap_id, val])

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        last_snap_id = bisect.bisect(self.history[index], [snap_id + 1]) - 1 # remember snap + 1
        return self.history[index][last_snap_id][1]

算法分析：

get时间复杂度为O(logn)，空间复杂度O(n), 数组某值n更改次数

暴力法算法II解题思路(不推荐)：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def __init__(self, length: int):
	self.ary = [0] * length
	self.snap_id = -1
	self.idx_snap_to_val = {}

def set(self, index: int, val: int) -> None:
	self.ary[index] = val

def snap(self) -> int:
	self.snap_id += 1
	for i, n in enumerate(self.ary):
		self.idx_snap_to_val[(i, self.snap_id)] = self.ary[i]
	return self.snap_id

def get(self, index: int, snap_id: int) -> int:
	return self.idx_snap_to_val[(index, snap_id)]

Free mock interview