跳至主要內容

1146. 快照数组

1146. 快照数组

🟠   🔖  设计 数组 哈希表 二分查找  🔗 力扣open in new window LeetCodeopen in new window

题目

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:

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 call snap())
  • At most 5 * 10^4 calls will be made to set, snap, and get.

题目大意

实现支持下列接口的「快照数组」- 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 是严格递增的，我们可以利用稀疏存储和二分查找来优化性能。

  1. 初始化 store：

    • 使用长度为 length 的数组 store 保存每个索引的值变化记录。
    • 对于每个索引 index，维护一个数组 [(snap_id1, value1), (snap_id2, value2), ...] 来记录不同快照编号对应的值。
    • 每个索引初始化为 [[0, 0]]，表示在 snap_id=0 时，默认值为 0。

  2. set(index, val)：

    • 在调用 set(index, val) 时，将 (snap_id, val) 插入到 store[index]，记录当前快照编号对应的值。
    • 注意只更新 index 的快照数组，而不是更新 store 中的所有快照数组，稀疏存储从而降低空间复杂度。
    • 例如，当 set(0, 5) 时，在 store[0] 中追加 [snap_id, 5]。

  3. snap()：

    • 返回当前快照编号 snap_id，然后将 snap_id 加 1。

  4. 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)
 */