LeetCode 1146. 快照数组

Categories:

题目描述
思路分析
1. 解法一：每个下标保存历史（推荐）
相似题目

题目描述

✅ 1146. 快照数组

思路分析

解法一：每个下标保存历史（推荐）

核心思路：

对每个下标维护一条 (snapId, value) 变更历史。

set 时若当前 snapId 已存在记录则覆盖，否则追加。

get 通过二分查找找到 snapId 不大于目标的最后记录。

复杂度分析：

时间复杂度：set 为 O(1)，get 为 O(log m)，其中 m 表示该下标的历史长度。

空间复杂度：O(n + t)，n 为数组长度，t 为变更次数。

class SnapshotArray {
    private int snapId = 0;
    private final List<int[]>[] history;

    public SnapshotArray(int length) {
        history = new ArrayList[length];
        for (int i = 0; i < length; i++) {
            history[i] = new ArrayList<>();
            history[i].add(new int[]{0, 0});
        }
    }

    public void set(int index, int val) {
        List<int[]> list = history[index];
        int[] last = list.get(list.size() - 1);

        if (last[0] == snapId) {
            // 同一快照内覆盖
            last[1] = val;
        } else {
            list.add(new int[]{snapId, val});
        }
    }

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

    public int get(int index, int snap_id) {
        List<int[]> list = history[index];

        int left = 0;
        int right = list.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid)[0] <= snap_id) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return list.get(right)[1];
    }
}

type Pair struct {
    snap int
    val  int
}

type SnapshotArray struct {
    snapId  int
    history [][]Pair
}

func Constructor(length int) SnapshotArray {
    history := make([][]Pair, length)
    for i := 0; i < length; i++ {
        history[i] = []Pair{{snap: 0, val: 0}}
    }

    return SnapshotArray{snapId: 0, history: history}
}

func (sa *SnapshotArray) Set(index int, val int) {
    list := sa.history[index]
    last := list[len(list)-1]

    if last.snap == sa.snapId {
        // 同一快照内覆盖
        list[len(list)-1].val = val
    } else {
        sa.history[index] = append(list, Pair{snap: sa.snapId, val: val})
    }
}

func (sa *SnapshotArray) Snap() int {
    id := sa.snapId
    sa.snapId++
    return id
}

func (sa *SnapshotArray) Get(index int, snapId int) int {
    list := sa.history[index]
    left, right := 0, len(list)-1

    for left <= right {
        mid := left + (right-left)/2
        if list[mid].snap <= snapId {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return list[right].val
}

相似题目

题目	难度	考察点
981. 基于时间的键值存储	中等	二分查找
303. 区域和检索 - 数组不可变	简单	前缀和
307. 区域和检索 - 数组可修改	中等	线段树
304. 二维区域和检索 - 矩阵不可变	中等	前缀和
284. 顶端迭代器	中等	迭代器

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/69888132