스냅샷 어레이

다음 인터페이스를 지원하는 SnapshotArray를 구현합니다.

SnapshotArray(int length) 주어진 길이로 배열과 유사한 데이터 구조를 초기화합니다. 처음에 각 요소는 0입니다.

void set(index, val)는 주어진 index의 요소를 val와 같게 설정합니다.

int snap() 배열의 스냅샷을 찍고 snap_id를 반환합니다. snap()에서 1를 뺀 총 횟수입니다.

int get(index, snap_id) 주어진 index의 값을 반환합니다. 이때 주어진 snap_id로 스냅샷을 찍었습니다.

예 1:

입력: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
출력: [널,널,0,널,5]
설명:
SnapshotArray snapshotArr = new SnapshotArray(3);//길이를 3으로 설정
snapshotArr.set(0,5);//배열[0] = 5로 설정
스냅샷Arr.snap();//스냅샷을 찍고, snap_id = 0을 반환합니다.
snapshotArr.set(0,6);
snapshotArr.get(0,0);//snap_id = 0으로 array[0]의 값을 가져오고, 5를 반환합니다.

제약:

1 <= length <= 50000

50000 , set 및 snap 에 최대 get 호출이 이루어집니다.

0 <= index < length

0 <= snap_id < (총 통화 횟수 snap() )

0 <= val <= 10^9

해결책:

class SnapshotArray:

    def __init__(self, length: int):
        self.snaps = {}
        self.sid = 0
        self.n = length

    def set(self, index: int, val: int) -> None:
        self.snaps[(self.sid, index)] = val

    def snap(self) -> int:
        res = self.sid
        self.sid += 1
        return res

    def getSnap(self, snap_id, index):
        for i in range(snap_id, -1, -1):
            if (i, index) in self.snaps:
                return self.snaps[(i, index)]
        return 0

    def get(self, index: int, snap_id: int) -> int:
        return self.getSnap(snap_id, index)

# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)