मैरीमा और न्यूनतम सरणी

Question

एन संख्याओं की एक सरणी दी जाती है, जहां एन भी एक संख्या है। अधिकतम और साथ ही इन एन संख्याओं में से न्यूनतम को निर्धारित करने की आवश्यकता है। मुझे आवश्यक तुलनाओं को जानने की आवश्यकता है?

Answer 1

यह ओ (एन) समय में किया जा सकता है।

आप संदर्भ

Answer 2

यह 3*n/2-2 तुलना उपयोग किया जा सकता के लिए इस link की जाँच कर सकते हैं।

n == 2 के लिए, बस दो संख्याओं की तुलना करें। अब मान लें कि हमारे पास पहले n-2 संख्याओं के लिए न्यूनतम और अधिकतम है। शेष दो संख्याओं की तुलना करें, फिर बड़े से अधिकतम की तुलना करें और छोटे से पिछले न्यूनतम की तुलना करें।

Answer 3

एक अनुरक्षित सरणी के लिए यह लगभग 1.5n तुलना में किया जा सकता है। आप इसे सरणी के तत्वों के जोड़ों की तुलना करके और min और स्थानीय max संग्रहीत करके कर सकते हैं। आपने मिनट खोजने के लिए n/2 तुलना (स्थानीय) अधिकतम और n/2 खोजने के लिए तुलना की है। इस प्रकार, इस चरण में कुल n।

अब आप अधिकतम और न्यूनतम स्थानीय लोगों पर जाएं और वैश्विक अधिकतम और न्यूनतम खोजें। यह n/2 तुलना भी लेगा। इस प्रकार n + n/2 = 1.5n।

सरणी सॉर्ट किया जाता है, तो आप, किसी भी तुलना बिना इसे पा सकते हैं के बाद से सबसे कम संख्या स्थिति 0 पर है और स्थिति एन पर उच्चतम - 1.