पायथन में स्नैपशॉट ऐरे

मान लीजिए कि हमें एक SnapshotArray लागू करना है जो निम्नलिखित इंटरफेस का समर्थन करता है -

• SnapshotArray(int length) यह दी गई लंबाई के साथ सरणी जैसी डेटा संरचना को इनिशियलाइज़ करेगा। प्रारंभ में, प्रत्येक तत्व 0 के बराबर होता है।

• सेट (इंडेक्स, वैल) यह दिए गए इंडेक्स पर तत्व को वैल के बराबर सेट करेगा।

• स्नैप () एरे का एक स्नैपशॉट लेगा और स्नैप_आईडी लौटाएगा:जितनी बार हमने स्नैप () माइनस 1 कहा।

• get(index, snap_id) यह दिए गए इंडेक्स पर मान लौटाएगा, जिस समय हमने दिए गए Snap_id के साथ स्नैपशॉट लिया था

तो यदि सरणी का आकार 2 है, तो इसे [0, 5] का उपयोग करके सेट किया जाता है, उसके बाद हम एक स्नैप लेते हैं, यह 0 लौटाएगा, फिर [0, 6] का उपयोग करके सेट करें, और प्राप्त करें (0, 0), यह वापस आ जाएगा 5.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• इनिशियलाइज़ करने का तरीका इस तरह होगा -

• वर्तमान:=0

• arr :=लंबाई की एक सरणी + 2d सरणियों की 1 संख्या [[0, 0]]

• सेट () विधि इस तरह होगी -

• अस्थायी:=गिरफ्तारी का अंतिम तत्व [सूचकांक]

• अगर अस्थायी [0] =वर्तमान, फिर गिरफ्तारी के अंतिम तत्व से सूचकांक 1 का तत्व [सूचकांक]:=वैल

• अन्यथा [वर्तमान, वैल] को एआर [इंडेक्स]

  में डालें

• स्नैप () विधि इस तरह होगी-

• करंट को 1 से बढ़ाएं, गिनती से एक कम लौटाएं

• प्राप्त () विधि इस तरह होगी -

• अस्थायी:=गिरफ्तारी [सूचकांक], निम्न:=0, उच्च:=अस्थायी की लंबाई – 1

• जबकि कम <उच्च

  • मध्य :=निम्न + (उच्च-निम्न)/2

  • अगर अस्थायी [मध्य, 0] <=स्नैप_आईडी, फिर निम्न:=मध्य, अन्यथा उच्च:=मध्य – 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