Python 中的快照数组

假设我们需要实现一个支持以下接口的 SnapshotArray：

  • SnapshotArray(int length) 这将使用给定长度初始化类似数组的数据结构。最初，每个元素都等于 0。

  • set(index, val) 这将设置给定索引处的元素等于 val。

  • snap() 将对数组进行快照并返回 snap_id：我们调用 snap() 的总次数减 1。

  • get(index, snap_id) 这将返回给定索引处的值，在使用给定 snap_id 拍摄快照时。

因此，如果数组大小为 2，则使用 [0, 5] 进行设置，之后我们进行快照，它将返回 0，然后使用 [0, 6] 进行设置，并且 get(0, 0) 将返回 5。

为了解决这个问题，我们将遵循以下步骤：

  • 初始化方法将如下所示：

  • current := 0

  • arr := 一个长度为 length + 1 的二维数组 [[0, 0]]

  • set() 方法将如下所示：

  • temp := arr[index] 的最后一个元素

  • 如果 temp[0] = current，则 arr[index] 的最后一个元素的索引 1 处的元素 := val

  • 否则将 [current, val] 插入 arr[index]

  • snap() 方法将如下所示：

  • 将 current 加 1，返回计数减 1

  • get() 方法将如下所示：

  • temp := arr[index]，low := 0，high := temp 的长度 – 1

  • 当 low < high 时

    • mid := low + (high – low) / 2

    • 如果 temp[mid, 0] <= snap_id，则 low := mid，否则 high := mid – 1

  • 返回 temp[low, 1]

示例（Python）

让我们看看以下实现以更好地理解：

 在线演示

class SnapshotArray(object):
   def __init__(self, length):
      self.current = 0
      self.arr = [[[0,0]] for i in range(length+1)]
   def set(self, index, val):
      temp = self.arr[index][-1]
      #print(temp)
      if temp[0] == self.current:
         self.arr[index][-1][1] = val
      else:
         self.arr[index].append([self.current,val])
   def snap(self):
      self.current+=1
      return self.current -1
   def get(self, index, snap_id):
      temp = self.arr[index]
      low = 0
      high = len(temp)-1
      while low < high:
         mid = low + (high - low+1 )//2
         if temp[mid][0]<=snap_id:
            low = mid
         else:
            high = mid -1
      return temp[low][1]
ob = SnapshotArray(3)
ob.set(0,5)
print(ob.snap())
ob.set(0,6)
print(ob.get(0,0))

输入

Initialize the array using 3, then call set(0,5), snap(), set(0,6), get(0, 0)

输出

0
5

更新于： 2020 年 4 月 30 日

518 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告