Medium

题目描述

实现支持下列接口的 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 的值。

示例 1：

输入：["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 <= 5 * 10^4
  • 0 <= index < length
  • 0 <= val <= 10^9
  • 0 <= snap_id < (调用 snap() 的总次数)
  • 最多调用 5 * 10^4 次 set、snap 和 get

提示：

  • 使用列表的列表，为每个索引添加元素和 snap_id。

解题思路

这个问题的核心挑战在于如何高效地存储和检索不同快照版本的数组状态。

朴素解法： 每次调用 snap() 时都完整复制一份数组。但这种方法空间复杂度很高，在频繁快照时会超出内存限制。

优化思路： 我们可以为每个数组索引维护一个版本历史，只记录实际发生变化的值。具体实现：

  1. 使用一个二维结构 history[index]，其中每个元素是 (snap_id, value) 对
  2. 在 set(index, val) 时，将当前快照ID和新值添加到对应索引的历史中
  3. 在 get(index, snap_id) 时，在该索引的历史中找到小于等于 snap_id 的最大快照ID对应的值

关键优化： 使用二分查找来快速定位历史记录中的正确版本，将查询时间复杂度从 O(n) 降低到 O(log n)。

初始化时，为每个索引添加一个初始记录 (0, 0)，确保即使没有设置过值也能正确查询到默认值 0。

这种设计既节省了空间（只存储变化），又保证了查询效率（二分查找）。

代码实现

class SnapshotArray {
private:
    vector<vector<pair<int, int>>> history;
    int currentSnapId;
    
public:
    SnapshotArray(int length) {
        history.resize(length);
        currentSnapId = 0;
        for (int i = 0; i < length; i++) {
            history[i].push_back({0, 0});
        }
    }
    
    void set(int index, int val) {
        if (history[index].back().first == currentSnapId) {
            history[index].back().second = val;
        } else {
            history[index].push_back({currentSnapId, val});
        }
    }
    
    int snap() {
        return currentSnapId++;
    }
    
    int get(int index, int snap_id) {
        auto& hist = history[index];
        int left = 0, right = hist.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (hist[mid].first <= snap_id) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return hist[left].second;
    }
};

class SnapshotArray:

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

    def set(self, index: int, val: int) -> None:
        if self.history[index][-1][0] == self.current_snap_id:
            self.history[index][-1] = (self.current_snap_id, val)
        else:
            self.history[index].append((self.current_snap_id, val))

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

    def get(self, index: int, snap_id: int) -> int:
        hist = self.history[index]
        left, right = 0, len(hist) - 1
        while left < right:
            mid = (left + right + 1) // 2
            if hist[mid][0] <= snap_id:
                left = mid
            else:
                right = mid - 1
        return hist[left][1]

public class SnapshotArray {
    private List<List<(int snapId, int val)>> history;
    private int currentSnapId;

    public SnapshotArray(int length) {
        history = new List<List<(int, int)>>();
        currentSnapId = 0;
        for (int i = 0; i < length; i++) {
            history.Add(new List<(int, int)> { (0, 0) });
        }
    }
    
    public void Set(int index, int val) {
        var hist = history[index];
        if (hist[hist.Count - 1].snapId == currentSnapId) {
            hist[hist.Count - 1] = (currentSnapId, val);
        } else {
            hist.Add((currentSnapId, val));
        }
    }
    
    public int Snap() {
        return currentSnapId++;
    }
    
    public int Get(int index, int snap_id) {
        var hist = history[index];
        int left = 0, right = hist.Count - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (hist[mid].snapId <= snap_id) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return hist[left].val;
    }
}

var SnapshotArray = function(length) {
    this.history = Array(length).fill(null).map(() => [[0, 0]]);
    this.currentSnapId = 0;
};

SnapshotArray.prototype.set = function(index, val) {
    const hist = this.history[index];
    if (hist[hist.length - 1][0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
SnapshotArray(length)O(length)O(length)
set(index, val)O(1)O(1)
snap()O(1)O(1)
get(index, snap_id)O(log S)O(1)

说明：

  • S 表示某个索引位置的历史记录数量
  • 总空间复杂度：O(length + total_sets)，其中 total_sets 是所有 set 操作的总次数
  • get 操作使用二分查找，时间复杂度为 O(log S)