Snapshot Array ใน 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] และรับ(0, 0) สิ่งนี้จะส่งคืน 5.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• วิธีการเริ่มต้นจะเป็นเช่น -

• ปัจจุบัน :=0

• arr :=อาร์เรย์ความยาว + 1 จำนวนอาร์เรย์ 2d [[0, 0]]

• วิธี set() จะเป็น −

• temp :=องค์ประกอบสุดท้ายของ arr[index]

• ถ้า temp[0] =ปัจจุบัน องค์ประกอบของดัชนี 1 จากองค์ประกอบสุดท้ายของ arr[index] :=val

• มิฉะนั้นให้แทรก [current, val] ลงใน arr[index]

• วิธี snap() จะเป็นเหมือน−

• เพิ่มกระแส 1 ส่งคืนน้อยกว่านับ

• get() วิธีการจะเป็นเช่น -

• temp :=arr[index], ต่ำ :=0, สูง :=ความยาวของอุณหภูมิ – 1

• ในขณะที่ต่ำ <สูง

  • กลาง :=ต่ำ + (สูง – ต่ำ) / 2

  • ถ้า temp[mid, 0] <=snap_id แล้ว low :=mid, มิฉะนั้น high :=mid – 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