1146. 快照数组

中等设计力扣原题 ↗

在线写代码并运行看动画推演问 AI 讲解

题目描述

设计一个支持快照的数组类 SnapshotArray。

SnapshotArray(length)：创建长度为 length 的数组，所有元素初值为 0。

set(index, val)：把下标 index 处的元素改为 val。下标从 0 开始。无返回值。

snap()：给当前数组拍一张快照，返回快照编号 snap_id。编号从 0 开始，等于此前调用 snap() 的次数。

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]

解释：先把 array[0] 设为 5，拍快照得到编号 0；之后改成 6 不影响快照，所以查询快照 0 得到 5。

数据范围

1 <= length <= 50000
set、snap、get 总共最多调用 50000 次。
0 <= index < length
0 <= snap_id < 已调用 snap() 的次数
0 <= val <= 10^9

解题思路

不要每次快照都复制整个数组。为每个下标保存一条修改历史 [(快照编号, 值), …]，编号按时间递增。set 记录在“当前尚未拍下的快照”snap_id 下，同一编号重复修改就覆盖最后一条。get(index, s) 在历史中二分查找最后一条编号 ≤ s 的记录。初始放一条 (-1, 0) 作为哨兵，保证一定能找到。

为什么正确

每条历史的快照编号严格递增；编号为 s 的快照中的值是编号 ≤ s 的最后一条记录。

复杂度分析

set 与 snap 为 O(1)，get 为 O(log m)（m 是该下标的修改次数）；空间 O(length + set 次数)。

易错点

set 记录的是当前 snap_id（下一张要拍的快照），不是上一张；在同一个 snap_id 内多次 set 要覆盖而不是追加，否则二分可能拿到旧值。二分找“最后一个满足条件”时 mid 要向上取整，否则 lo = mid 会死循环。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

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

    def set(self, index: int, val: int) -> None:
        h = self.hist[index]
        if h[-1][0] == self.snap_id:
            h[-1] = (self.snap_id, val)
        else:
            h.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:
        h = self.hist[index]
        lo, hi = 0, len(h) - 1
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if h[mid][0] <= snap_id:
                lo = mid
            else:
                hi = mid - 1
        return h[lo][1]

class SnapshotArray {
    private List<List<int[]>> hist;
    private int snapId;

    public SnapshotArray(int length) {
        hist = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            List<int[]> h = new ArrayList<>();
            h.add(new int[]{-1, 0});
            hist.add(h);
        }
        snapId = 0;
    }

    public void set(int index, int val) {
        List<int[]> h = hist.get(index);
        if (h.get(h.size() - 1)[0] == snapId) {
            h.set(h.size() - 1, new int[]{snapId, val});
        } else {
            h.add(new int[]{snapId, val});
        }
    }

    public int snap() {
        snapId++;
        return snapId - 1;
    }

    public int get(int index, int snap_id) {
        List<int[]> h = hist.get(index);
        int lo = 0, hi = h.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (h.get(mid)[0] <= snap_id) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        return h.get(lo)[1];
    }
}

class SnapshotArray {
public:
    vector<vector<pair<int, int>>> hist;
    int snap_id;

    SnapshotArray(int length) {
        hist.assign(length, vector<pair<int, int>>{{-1, 0}});
        snap_id = 0;
    }

    void set(int index, int val) {
        auto& h = hist[index];
        if (h.back().first == snap_id) {
            h.back() = {snap_id, val};
        } else {
            h.push_back({snap_id, val});
        }
    }

    int snap() {
        snap_id++;
        return snap_id - 1;
    }

    int get(int index, int snap_id) {
        auto& h = hist[index];
        int lo = 0, hi = h.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (h[mid].first <= snap_id) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        return h[lo].second;
    }
};

type SnapshotArray struct {
	hist   [][][2]int
	snapId int
}

func Constructor(length int) SnapshotArray {
	hist := make([][][2]int, length)
	for i := range hist {
		hist[i] = [][2]int{{-1, 0}}
	}
	return SnapshotArray{hist: hist, snapId: 0}
}

func (this *SnapshotArray) Set(index int, val int) {
	h := this.hist[index]
	if h[len(h)-1][0] == this.snapId {
		h[len(h)-1] = [2]int{this.snapId, val}
	} else {
		this.hist[index] = append(h, [2]int{this.snapId, val})
	}
}

func (this *SnapshotArray) Snap() int {
	this.snapId++
	return this.snapId - 1
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
	h := this.hist[index]
	lo, hi := 0, len(h)-1
	for lo < hi {
		mid := (lo + hi + 1) / 2
		if h[mid][0] <= snap_id {
			lo = mid
		} else {
			hi = mid - 1
		}
	}
	return h[lo][1]
}

class SnapshotArray {
    constructor(length) {
        this.hist = Array.from({ length }, () => [[-1, 0]]);
        this.snapId = 0;
    }

    set(index, val) {
        const h = this.hist[index];
        if (h[h.length - 1][0] === this.snapId) {
            h[h.length - 1] = [this.snapId, val];
        } else {
            h.push([this.snapId, val]);
        }
    }

    snap() {
        this.snapId++;
        return this.snapId - 1;
    }

    get(index, snap_id) {
        const h = this.hist[index];
        let lo = 0, hi = h.length - 1;
        while (lo < hi) {
            const mid = (lo + hi + 1) >> 1;
            if (h[mid][0] <= snap_id) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        return h[lo][1];
    }
}

class SnapshotArray {
    hist: number[][][];
    snapId: number;

    constructor(length: number) {
        this.hist = Array.from({ length }, () => [[-1, 0]]);
        this.snapId = 0;
    }

    set(index: number, val: number): void {
        const h = this.hist[index];
        if (h[h.length - 1][0] === this.snapId) {
            h[h.length - 1] = [this.snapId, val];
        } else {
            h.push([this.snapId, val]);
        }
    }

    snap(): number {
        this.snapId++;
        return this.snapId - 1;
    }

    get(index: number, snap_id: number): number {
        const h = this.hist[index];
        let lo = 0, hi = h.length - 1;
        while (lo < hi) {
            const mid = (lo + hi + 1) >> 1;
            if (h[mid][0] <= snap_id) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        return h[lo][1];
    }
}

载入编辑器，自己跑一遍 →

设计专题的其他题目

查看设计全部题目 →