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

मान लीजिए हमें एक 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 लौटाएगा।

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

• इनिशियलाइज़ मेथड इस तरह होगा -

• current := 0

• arr := लंबाई + 1 संख्या के 2d ऐरे [[0, 0]]

• set() मेथड इस तरह होगा -

• temp := arr[index] का अंतिम एलिमेंट

• यदि temp[0] = current, तो arr[index] के अंतिम एलिमेंट के इंडेक्स 1 का एलिमेंट := val

• अन्यथा [current, val] को arr[index] में इन्सर्ट करें

• snap() मेथड इस तरह होगा-

• current को 1 से बढ़ाएं, काउंट से एक कम लौटाएं

• get() मेथड इस तरह होगा -

• temp := arr[index], low := 0, high := temp की लंबाई - 1

• जब तक low < high

  • mid := low + (high - low) / 2

  • यदि temp[mid, 0] <= snap_id, तो low := mid, अन्यथा high := mid - 1

• temp[low, 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]
        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))

इनपुट

3 का उपयोग करके ऐरे इनिशियलाइज़ करें, फिर set(0,5), snap(), set(0,6), get(0, 0) कॉल करें

आउटपुट

0
5