एक सरणी में जाँच करने का सबसे अच्छा तरीका क्या है यदि A नामक एक सरणी में 2 संख्याएँ X, Y हैं, जो X + Y = S. S कोई भी संख्या हो सकती है (जरूरी नहीं कि A में मौजूद हो)।

मैंने कहा, आइए उस सरणी को क्रमबद्ध करें जिसकी सबसे खराब स्थिति के लिए O(nlogn) खर्च होता है तो चलिए पहले तत्व के लिए 2 पॉइंटर लेते हैं और अंतिम तत्व के लिए दूसरा पॉइंटर लेते हैं।

यदि सूचक 1 + सूचक 2 है तो तुलना प्रारंभ करें। यदि परिणाम बड़ा है तो घटाना सूचक 2 को 1 से कम करें। यदि परिणाम छोटा है तो सूचक 1 को 1 से बढ़ाएं। जब तक हम ए में सभी एल्स पर आगे नहीं बढ़ते।

समय जटिलता: nlogn + n(२ पॉइंटर्स में जाने के लिए सबसे खराब स्थिति) = nlogn.

क्या कोई बेहतर उपाय है?

0
Gladiatorr 22 जिंदा 2020, 23:40

1 उत्तर

सबसे बढ़िया उत्तर

आप हैश-आधारित सेट बना सकते हैं और इसमें ए से सभी तत्व जोड़ सकते हैं। फिर आप ए तत्वों के माध्यम से पुनरावृति कर सकते हैं और जांच सकते हैं कि इस सेट में एस - ए_आई मौजूद है या नहीं। यह मानते हुए कि ओ (1) में हैश-आधारित सेट कार्य पर संचालन शामिल है और आप ओ (एन) में अपनी समस्या का समाधान करेंगे।

2
ardenit 22 जिंदा 2020, 23:45