다음 인터페이스를 지원하는 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 :=길이의 배열 + 1개의 2차원 배열 [[0, 0]]
-
set() 메서드는 다음과 같습니다 -
-
temp :=arr[인덱스]
의 마지막 요소 -
temp[0] =현재이면 arr[index]의 마지막 요소에서 인덱스 1의 요소:=val
-
그렇지 않으면 [current, val]을 arr[index]
에 삽입합니다. -
snap() 메서드는 다음과 같습니다-
-
전류를 1만큼 증가시키고 count보다 하나 작은 값을 반환합니다.
-
get() 메서드는 다음과 같습니다 -
-
temp :=arr[index], low :=0, high :=temp의 길이 – 1
-
낮음 <높음
동안-
중간 :=낮음 + (높음 – 낮음) / 2
-
temp[mid, 0] <=snap_id이면 low :=mid, 그렇지 않으면 high :=mid – 1
-
-
반환 온도[낮음, 1]
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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