1146. 快照数组
1146. 快照数组
🟠 🔖 设计
数组
哈希表
二分查找
🔗 力扣
LeetCode
题目
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 givenindex
to be equal toval
.int snap()
takes a snapshot of the array and returns thesnap_id
: the total number of times we calledsnap()
minus1
.int get(index, snap_id)
returns the value at the givenindex
, at the time we took the snapshot with the givensnap_id
Example 1:
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 <= 5 * 10^4
0 <= index < length
0 <= val <= 10^9
0 <= snap_id <
(the total number of times we callsnap()
)- At most
5 * 10^4
calls will be made toset
,snap
, andget
.
题目大意
实现支持下列接口的「快照数组」- 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
的值。
示例:
输入:["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 <= length <= 50000
- 题目最多进行
50000
次set
,snap
,和get
的调用 。 0 <= index < length
0 <= snap_id <
我们调用snap()
的总次数0 <= val <= 10^9
解题思路
由于 snap_id
是严格递增的,我们可以利用稀疏存储和二分查找来优化性能。
初始化
store
:- 使用长度为
length
的数组store
保存每个索引的值变化记录。 - 对于每个索引
index
,维护一个数组[(snap_id1, value1), (snap_id2, value2), ...]
来记录不同快照编号对应的值。 - 每个索引初始化为
[[0, 0]]
,表示在snap_id=0
时,默认值为 0。
- 使用长度为
set(index, val)
:- 在调用
set(index, val)
时,将(snap_id, val)
插入到store[index]
,记录当前快照编号对应的值。 - 注意只更新
index
的快照数组,而不是更新store
中的所有快照数组,稀疏存储从而降低空间复杂度。 - 例如,当
set(0, 5)
时,在store[0]
中追加[snap_id, 5]
。
- 在调用
snap()
:- 返回当前快照编号
snap_id
,然后将snap_id
加 1。
- 返回当前快照编号
get(index, snap_id)
:- 对
store[index]
使用二分查找,找到最后一个小于等于snap_id
的编号,返回对应的值。
- 对
复杂度分析
- 时间复杂度:
set
操作:O(1)
,直接追加新值。snap
操作:O(1)
,只返回并更新快照编号。get
操作:O(log n)
,二分查找快照编号。
- 空间复杂度:
O(m)
,假设进行了m
次set
操作,则store
的空间复杂度为O(m)
,仅存储变化值而不是每次完整快照。
代码
class SnapshotArray {
/**
* @param {number} length
*/
constructor(length) {
this.snap_id = 0; // 当前快照编号
this.store = new Array(length).fill().map(() => new Array(1).fill([0, 0])); // 每个索引存储 [(snap_id, value)]
}
/**
* @param {number} index
* @param {number} val
* @return {void}
*/
set(index, val) {
// 新增一个快照记录
this.store[index].push([this.snap_id, val]);
}
/**
* @return {number}
*/
snap() {
return this.snap_id++;
}
/**
* @param {number} index
* @param {number} snap_id
* @return {number}
*/
get(index, snap_id) {
const arr = this.store[index];
let left = 0,
right = arr.length - 1;
let res = 0;
// 二分查找最后一个小于等于 snap_id 的快照编号
while (left <= right) {
const mid = ((left + right) / 2) | 0;
if (arr[mid][0] > snap_id) {
right = mid - 1;
} else {
res = arr[mid][1];
left = mid + 1;
}
}
return res;
}
}
/**
* Your SnapshotArray object will be instantiated and called as such:
* var obj = new SnapshotArray(length)
* obj.set(index,val)
* var param_2 = obj.snap()
* var param_3 = obj.get(index,snap_id)
*/