Mảng ảnh chụp nhanh bằng Python

Giả sử chúng ta phải triển khai SnapshotArray hỗ trợ các giao diện sau -

• SnapshotArray (int length) sẽ khởi tạo cấu trúc dữ liệu dạng mảng với độ dài đã cho. Ban đầu, mỗi phần tử bằng 0.

• set (index, val), điều này sẽ đặt phần tử ở chỉ số đã cho bằng val.

• snap () sẽ chụp nhanh mảng và trả về snap_id:tổng số lần chúng tôi gọi là snap () trừ đi 1.

• get (index, snap_id), giá trị này sẽ trả về giá trị tại chỉ mục nhất định, tại thời điểm chúng tôi chụp nhanh với snap_id đã cho

Vì vậy, nếu kích thước mảng là 2, nó được đặt bằng [0, 5], sau đó chúng ta chụp nhanh, nó sẽ trả về 0, sau đó đặt bằng [0, 6] và get (0, 0), giá trị này sẽ trả về 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Phương thức khởi tạo sẽ giống như -

• hiện tại:=0

• arr:=một mảng độ dài + 1 số mảng 2d [[0, 0]]

• Phương thức set () sẽ giống như -

• temp:=phần tử cuối cùng của arr [index]

• nếu temp [0] =current, thì phần tử của chỉ mục 1 từ phần tử cuối cùng của arr [index]:=val

• nếu không thì chèn [current, val] vào arr [index]

• Phương thức snap () sẽ giống như−

• tăng dòng điện lên 1, trả về một ít hơn số đếm

• Phương thức get () sẽ giống như -

• temp:=arr [index], low:=0, high:=length of temp - 1

• trong khi thấp

  • giữa:=low + (cao - thấp) / 2

  • nếu temp [mid, 0] <=snap_id thì low:=mid, ngược lại high:=mid - 1

• nhiệt độ trả về [thấp, 1]

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

Initialize the array using 3, then call set(0,5), snap(), set(0,6), get(0, 0)

Đầu ra

0
5