Python中的快照数组
假设我们必须实现一个支持以下接口的SnapshotArray-
SnapshotArray（intlength）这将使用给定的长度初始化类似数组的数据结构。最初，每个元素等于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