मान लीजिए हम एक डेटा संरचना बनाना चाहते हैं जिसमें दो तरीके हों -
- जोड़ें (वैल) यह डेटा संरचना में मूल्य वैल जोड़ता है
- ढूंढें (वैल) यह जांचता है कि क्या दो तत्व हैं जिनका योग वैल है या नहीं
हमें इसे डिजाइन करना होगा ताकि हम तुरंत परिणाम प्राप्त कर सकें। हर बार जब कोई प्रश्न आता है तो हम संख्याओं की खोज नहीं करेंगे।
इसलिए, यदि इनपुट एक ऑब्जेक्ट obj बनाने जैसा है और कुछ संख्याएँ 6, 14, 3, 8, 11, 15 जोड़ें, तो checklike obj.find(9), obj.find(11), obj.find(15), तो आउटपुट ट्रू, ट्रू, असत्य होगा क्योंकि 9 को 6+3, 11 को 3+8 से बनाया जा सकता है। अब डेटा संरचना में 15 मौजूद है लेकिन दो संख्याओं का योग 15 के समान नहीं है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- कन्स्ट्रक्टर को परिभाषित करें।
- अंक:=एक नया सेट
- एकाधिक:=एक नया सेट
- एक फंक्शन ऐड () को परिभाषित करें। इसमें वैल लगेगा
- एकाधिक में वैल डालें
- अन्यथा,
- अंकों में वैल डालें
- एक फ़ंक्शन को परिभाषित करें find() । इसमें वैल लगेगा
- अंकों में प्रत्येक n के लिए, करें
- यदि n + n वैल के समान है, तो
- सही लौटें जब n एकाधिक में हो
- अन्यथा जब वैल - n अंकों में हो, तो
- सही लौटें
- यदि n + n वैल के समान है, तो
- झूठी वापसी
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
class PairSumChecker: def __init__(self): self.nums = set() self.multiple = set() def add(self, val): if val in self.nums: self.multiple.add(val) else: self.nums.add(val) def find(self, val): for n in self.nums: if n + n == val: return n in self.multiple elif val - n in self.nums: return True return False obj = PairSumChecker() obj.add(6) obj.add(14) obj.add(3) obj.add(8) obj.add(11) obj.add(15) print(obj.find(9)) print(obj.find(11)) print(obj.find(15))
इनपुट
print(obj.find(9)) print(obj.find(11)) print(obj.find(15))
आउटपुट
True True False