資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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
518 次檢視
