मान लीजिए हमारे पास एक डेटा संरचना है जो औसत O(1) समय में निम्न सभी ऑपरेशन्स का समर्थन करती है।
insert(val) - यह आइटम val को सेट में इन्सर्ट करेगा यदि वह पहले से मौजूद नहीं है।
remove(val) - यह आइटम val को सेट से हटा देगा यदि यह मौजूद है।
getRandom - यह वर्तमान सेट के एलिमेंट्स से एक रैंडम एलिमेंट लौटाएगा। प्रत्येक एलिमेंट की वापस आने की समान संभावना होनी चाहिए।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
इनिशियलाइज़ेशन के लिए, एक पैरेंट मैप और एलिमेंट्स ऐरे परिभाषित करें
insert() फंक्शन के लिए, यह val इनपुट के रूप में लेगा
यदि val पैरेंट मैप में मौजूद नहीं है, या parent[val] = 0, तो val को एलिमेंट्स में इन्सर्ट करें, और parent[val] := 1 सेट करें, और true लौटाएं
false लौटाएं
remove() मेथड के लिए, यह हटाने के लिए val लेगा
यदि val पैरेंट मैप में मौजूद नहीं है, या parent[val] = 0, तो false लौटाएं
parent[val] := 0 सेट करें
index := एलिमेंट्स ऐरे में val का इंडेक्स
यदि index एलिमेंट्स की लंबाई - 1 के समान नहीं है
temp := एलिमेंट्स का अंतिम एलिमेंट
एलिमेंट्स का अंतिम एलिमेंट := val सेट करें
elements[index] := temp सेट करें
एलिमेंट्स का अंतिम एलिमेंट हटाएं
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())इनपुट
क्लास इनिशियलाइज़ करें, फिर insert(), remove(), getRandom() फंक्शन्स कॉल करें। कार्यान्वयन देखें।
आउटपुट
True False True 2 True False 2
