यह एक साक्षात्कार प्रश्न है। एक क्रमबद्ध पूर्णांक सरणी और संख्या जेड को सरणी में सभी जोड़े (x, y) को ढूंढें ताकि x + y < z। क्या यह ओ (एन^2) से बेहतर किया जा सकता है?एक क्रमबद्ध सरणी में सभी जोड़े (x, y) खोजें ताकि x + y <z
पीएस मुझे पता है कि हम ओ (एन) में सभी जोड़े (x, y | x + y == z) पा सकते हैं।
आप जरूरी हे में सभी तरह के जोड़े नहीं मिल सकता है (एन) समय है, क्योंकि वहाँ O (n) मान इस संपत्ति है कि जोड़े के हो सकता है। आम तौर पर, एक एल्गोरिदम इसे उत्पन्न होने वाले मानों की संख्या से चलाने के लिए कम समय नहीं ले सकता है।
आशा है कि इससे मदद मिलती है!
उत्पन्न करने में, नहीं, यह नहीं कर सकता। उस मामले पर विचार करें जहां सभी x, y सरणी में है। सेट में संभावित जोड़े को n(n - 1)/2 सभी को स्पर्श करना होगा (उदा। प्रदर्शित करना)। यह मौलिक रूप से ओ (एन^2) है।
आप उन्हें ओ (एन) में देख सकते हैं, यदि आप अतिरिक्त तत्व जोड़ते हैं तो प्रत्येक तत्व अद्वितीय है।
सभी x + y == z जोड़े खोजने के बाद, आप जानते हैं कि प्रत्येक एक्स और वाई के लिए जो उस शर्त को संतुष्ट करता है, प्रत्येक एक्स या वाई (एक चुनें) जो कि इसकी जोड़ी की तुलना में कम इंडेक्स पर है x + वाई < जेड हालत।
असल में इन्हें चुनकर और उन्हें आउटपुट करने से ओ (एन^2) लगेगा, लेकिन एक अर्थ में, x + y == z जोड़े इनपुट के साथ एक साथ संकुचित रूप हैं।
(आप इनपुट को प्रीप्रोसेस कर सकते हैं जहां प्रत्येक तत्व अद्वितीय है, साथ ही घटनाओं की संख्या के लिए काउंटर के साथ। इसमें ओ (एन) समय लगेगा। आप इस समाधान को बिना छेड़छाड़ वाले सरणी में सामान्य कर सकते हैं, समय बढ़ा सकते हैं ओ (nlogn)।)
यह कहने का औचित्य कि समाधान के आकार के लिए रैखिक आनुपातिक समय के भीतर जोड़े को ढूंढना: मान लीजिए कि प्रश्न "0 और दिए गए इनपुट के बीच के पूर्णांक क्या हैं" ?
यदि आपको उस संपत्ति को संतुष्ट करने वाले सभी जोड़े को आउटपुट करने के लिए कहा जाता है, तो मुझे नहीं लगता कि ओ (एन^2) से बेहतर कुछ भी है क्योंकि आउटपुट में ओ (एन^2) जोड़े हो सकते हैं।
लेकिन यह x + y = z के लिए भी सच है, जिसके लिए आप दावा करते हैं कि ओ (एन) समाधान है - इसलिए मुझे कुछ याद आ रहा है।
मुझे संदेह है कि मूल प्रश्न पूछा गया है कि जोड़े की संख्या के लिए पूछा गया है। उस स्थिति में, यह ओ (एन लॉग (एन)) में किया जा सकता है। प्रत्येक तत्व x के लिए y = z - x ढूंढें और सरणी में y के लिए बाइनरी खोज करें। वाई की स्थिति जोड़ों की संख्या देता है जिसे एक्स के उस विशेष मूल्य के साथ बनाया जा सकता है। सरणी में सभी मानों पर इसे सारांशित करने से आपको जवाब मिल जाता है। एन मान हैं और संख्या को ढूंढते हैं यदि प्रत्येक के लिए जोड़े ओ (लॉग (एन)) (बाइनरी खोज) लेता है, तो पूरी बात ओ (एन लॉग (एन)) है।
क्योंकि यह एक अनुसार क्रमबद्ध पूर्णांक सरणी है, तो आप द्विआधारी खोज एल्गोरिथ्म इस्तेमाल कर सकते हैं, तो सबसे अच्छा O(N) है, और सबसे खराब O(N*logN) है, औसत मामला भी O(N*logN) है।
आप सरणी को सॉर्ट कर सकते हैं और जेड से कम प्रत्येक तत्व के लिए, बाइनरी-सर्च - कुल ओ (एनएलओएनएन) का उपयोग कर सकते हैं।
कुल रन-टाइम: ओ (| पी | + एनएलएलएन), जहां पी परिणामस्वरूप जोड़े हैं।
वास्तव में इस प्रश्न के लिए एक ओ (nlogn) समाधान मौजूद है। मैं क्या करूंगा (अगर मुझे ऐसा करने की अनुमति है तो पहले जांच करने के बाद) मेरे एल्गोरिदम/फ़ंक्शन के आउटपुट प्रारूप को परिभाषित करना है।
मैं इसे तत्वों (एस, टी) के अनुक्रम के रूप में परिभाषित करता हूं। एस - सरणी में तत्व की स्थिति (या इसके मूल्य)। टी - उप-सरणी की स्थिति [0, टी]। तो उदाहरण के लिए, यदि टी = 3, तो इसका मतलब है कि तत्व एस 0 तत्वों के साथ संयुक्त 0,1,2 और 3 वांछित स्थिति को पूरा करते हैं।
इसका कुल परिणाम ओ (nlogn) रन टाइम, और ओ (एन) मेमोरी है।
जबकि मैं पूरी तरह से आपके अवलोकन से सहमत हूं, आउटपुट "प्रारूप" को परिभाषित करने की हमारी क्षमता के बारे में मेरी टिप्पणी देखें। – ZeDuS