एक कतार डिजाइन जो getMedian फ़ंक्शन

Question

का समर्थन करता है यह एक साक्षात्कार प्रश्न है। आपको एक कतार डिजाइन करने की आवश्यकता है जिसमें पूर्णांक मान होते हैं और एक मेडेडियन() फ़ंक्शन होता है जो वर्तमान कतार का औसत तत्व देता है। आप ओ (एन) अतिरिक्त जगह का उपयोग कर सकते हैं।

प्राप्त कर सकते हैं मेडियन() समय जटिलता < ओ (एन) के साथ लागू किया जा सकता है?

उदाहरण के लिए: कतार निम्न मान होते हैं (2, 1, 2, 2, 6, 4, 2, 5) इस विधि रिटर्न 2 और उस वस्तु को दूर नहीं करता।

Answer 1

आपकी समस्या के लिए जाना जाता कार्यान्वयन के रूप में तो यह है:

क्या क्रियान्वित करना चाहिए, 2 ढेर है, एक एक मिनट-ढेर और अन्य एक अधिकतम-ढेर हो जाएगा।
इसके अलावा आपको अपनी कतार में वस्तुओं की संख्या बताने के लिए एक पूर्णांक की आवश्यकता होगी।

ढेर के लिए की कमी इस प्रकार हैं:
1. मिनट-ढेर अपने कतार का बड़ा वस्तुओं होगा
2. अधिकतम-ढेर अपने कतार
3. की ​​छोटी वस्तुओं होगा अधिकतम-ढेर होता है या आपका मिनट-ढेर

इस तरह से कम 1 अधिक वस्तु होगा, अगर आप वस्तुओं की एक विषम संख्या है मंझला वास्तव में अपनी अधिकतम-ढेर में अधिकतम वस्तु होगा। यदि आपके पास ऑब्जेक्ट्स की संख्या भी है तो आपका औसत आपके ढेर की जड़ों (अधिकतम अधिकतम ढेर, न्यूनतम-ढेर का न्यूनतम) का औसत होगा।

यह ध्यान रखना महत्वपूर्ण है कि यदि आपका ढेर असमान हो जाता है, उदाहरण के लिए यदि आप एक निश्चित ढेर से "पॉप" करेंगे, तो आपको अन्य ढेर से हटाना होगा और इसे स्थानांतरित करना होगा। लेकिन यह कोई समस्या नहीं है जितना आपको निपटने की ज़रूरत है वह आपके ढेर की जड़ें और कुछ और नहीं है।

getMedian के समय जटिलता हे हो जाता है (1)

बस इस विषय पर एक लेख मिला: link

उत्तर टिप्पणी करने के लिए

अधिकतम-ढेर रखती आधा छोटी से छोटी तत्वों।
जब आप कतार में कोई नया नंबर जोड़ते हैं, तो आप पहले जांच लें कि कतार में ऑब्जेक्ट्स की संख्या क्या है।
यदि आप जो संख्या जोड़ रहे हैं वह एक संख्या भी है, तो इसका मतलब है कि इसे अधिकतम-ढेर में जोड़ा जाना चाहिए क्योंकि दोनों कतार आकार के बराबर हैं।
फिर आप देखते हैं कि अधिकतम-ढेर में अधिकतम क्या है।
यदि यह आपके नंबर से बड़ा है, तो आप इसे अधिकतम-ढेर में डाल सकते हैं।
यदि यह छोटा है, तो आपका नया नंबर न्यूनतम-ढेर में एक संख्या से बड़ा हो सकता है।
तो आप देखते हैं कि न्यूनतम-ढेर में न्यूनतम क्या है।
यदि आपका नंबर न्यूनतम से छोटा है, तो आप अधिकतम-ढेर में इसे सम्मिलित कर सकते हैं, यदि यह बड़ा है, तो आप मिनट को अधिकतम-ढेर में अधिकतम-ढेर में ले जाएं, और अपना नया नंबर डालें मिनट-ढेर।
यदि संख्या एक विषम संख्या है, तो आपको न्यूनतम-ढेर में जोड़ना होगा क्योंकि अधिकतम-ढेर में एक और है, और इसी तरह ..

इसके थोड़ा जटिल है, लेकिन अगर आप अभी भी न समझ में मैं तुम्हारे लिए यह कोडिंग