设计快照数组(LeetCode 1146)
哪些公司问过
答案要点
- 每个下标维护 (snap_id, val) 历史列表,避免每次 snap 全量复制
- set:最后一条快照号等于当前 snapId 时覆盖,否则追加,保证列表有序
- snap:返回当前 snapId 并自增,O(1)
- get:二分找快照号 ≤ 目标的最后一条,不存在返回 0
- 复杂度:set、snap O(1),get O(log m),空间与修改次数成正比
易错点
- 每次 snap 复制整个数组,导致超时或爆内存
- 二分边界写错,返回了大于目标快照的值
- 没处理从未修改过的下标,应返回 0
面试官常见追问
- 为什么同一快照内多次 set 要覆盖而不是追加?
- 如果下标很稀疏、长度很大怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。