发表于 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 题目链接