मान लीजिए कि हमारे पास एक डेटा संरचना है जो औसत O(1) समय में निम्नलिखित सभी कार्यों का समर्थन करती है।
-
insert(val) - यदि यह पहले से मौजूद नहीं है तो यह सेट में एक आइटम वैल सम्मिलित करेगा।
-
remove(val) - यदि यह प्रस्तुत करता है तो यह सेट से एक आइटम वैल को हटा देगा।
-
getRandom - यह तत्वों के वर्तमान सेट से एक यादृच्छिक तत्व लौटाएगा। प्रत्येक तत्व के वापस आने की संभावना समान होनी चाहिए।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
इनिशियलाइज़ेशन के लिए, पैरेंट मैप और एलीमेंट ऐरे को परिभाषित करें
-
इन्सर्ट () फ़ंक्शन के लिए, यह इनपुट के रूप में वैल लेगा
-
अगर वैल पैरेंट मैप में मौजूद नहीं है, या पैरेंट [वैल] =0, तो तत्वों में वैल डालें, और पैरेंट [वैल] सेट करें:=1 और सही लौटें
-
-
झूठी वापसी
-
हटाने () विधि के लिए, इसे हटाने के लिए वैल लगेगा
-
अगर वैल पैरेंट मैप में मौजूद नहीं है, या पैरेंट[वैल] =0, तो गलत लौटाएं
-
पैरेंट सेट करें [वैल] :=0
-
अनुक्रमणिका:=तत्वों की सरणी में वैल का सूचकांक
-
यदि सूचकांक तत्वों की लंबाई के समान नहीं है - 1
-
अस्थायी:=तत्वों का अंतिम तत्व
-
तत्वों का अंतिम तत्व सेट करें:=वैल
-
तत्वों को सेट करें [सूचकांक]:=अस्थायी
-
-
तत्वों का अंतिम तत्व हटाएं
-
GetRandom () विधि तत्व सरणी में मौजूद किसी भी यादृच्छिक मान को वापस कर देगी
उदाहरण (पायथन)
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
import random
class RandomizedSet(object):
def __init__(self):
self.present = {}
self.elements = []
def insert(self, val):
if val not in self.present or self.present[val] == 0:
self.elements.append(val)
self.present[val] = 1
return True
return False
def remove(self, val):
if val not in self.present or self.present[val] == 0:
return False
self.present[val] = 0
index = self.elements.index(val)
if index!=len(self.elements)-1:
temp = self.elements[-1]
self.elements[-1] = val
self.elements[index]=temp
self.elements.pop()
return True
def getRandom(self):
return random.choice(self.elements)
ob = RandomizedSet()
print(ob.insert(1))
print(ob.remove(2))
print(ob.insert(2))
print(ob.getRandom())
print(ob.remove(1))
print(ob.insert(2))
print(ob.getRandom()) इनपुट
Initialize the class, then call the insert(), remove(), getRandom() functions. See the implementation.
आउटपुट
True False True 2 True False 2