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，

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

• 初始化方法将类似于-

• 当前：= 0

• arr：=一个长度为数组+ 12d数组[[0，0]]

• 该set()方法将像-

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

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

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

• 该snap()方法将是-

• 将电流增加1，返回小于计数值1

• 该get()方法将像-

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

• 从低到高

• 中：=低+（高–低）/ 2

• 如果temp [mid，0] <= snap_id，则低：=中，否则高：=中– 1

• 返回温度[低，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