JZX轻语：简

LeetCode 1146 - 快照数组

发表于2024年04月26日

#二分法 #数组

简单想法是每次快照时，都存一份完整的列表，但这样会导致内存超限。优化思路类似于开散列法的哈希表。其中每个索引self._arr[i]使用一个桶来存储快照信息，其元素为一个记录快照id和值的元组(snap_id, val)。只有调用set保存的时候，才针对index新建一个快照信息。当使用get查询某个索引index内特定快照snap_id的值时，使用二分法搜索桶内self._arr[index]快照id小于等于snap_id最大者，并提取出val即可。

class SnapshotArray:

    def __init__(self, length: int):
        self._arr = [[(0, 0)] for _ in range(length)]
        self._next_snap = 0  # 下一次的快照id

    def set(self, index: int, val: int) -> None:
        last_snap, _ = self._arr[index][-1]
        if last_snap == self._next_snap:  # 本次快照已经有值
            self._arr[index][-1] = (self._next_snap, val)
        else:  # 否则新建一个快照状态
            self._arr[index].append((self._next_snap, val))

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

    def get(self, index: int, snap_id: int) -> int:
        # 二分查找小于等于snap_id的最大值
        lo, hi = 0, len(self._arr[index]) - 1
        while lo <= hi:
            mid = (lo + hi) >> 1
            if self._arr[index][mid][0] > snap_id:
                hi = mid - 1
            else:
                lo = mid + 1
        return self._arr[index][hi][1]

闪念标签：LC

题目链接：https://leetcode.cn/problems/snapshot-array/