विशिष्ट मानों के साथ ऐरे

Question

एन के आकार को एक सरणी को देखते हुए: सरणी का 1/2 एक एकल (अज्ञात) मान के साथ है। सरणी का 1/4 एक एकल (अज्ञात) अलग मान के साथ है। और इतने पर 1/8, 1/16, 1/32 सरणी को सॉर्ट करने के लिए एल्गोरिदम दें। आप उपयोग नहीं कर सकते मंझला एल्गोरिथ्म खोजने के

तो क्या मैं लगा है: केवल logn विभिन्न मूल्यों एक सरल हे पर एक द्विआधारी ढेर का उपयोग कर समाधान नहीं है कर रहे हैं (एन * loglogn) यह एक सवाल है कि जरूरत की तरह दिखता है (एन) ओ में हल किया जा करने के लिए

Answer 1

विचार अधिकांश एल्गोरिथ्म कि हे (एन) लेता है तो क्या है की खोज "आधा" मान सरणी से हटाने है करके पुन: चालू कर उपयोग करने के लिए है है नई सरणी n + n/2 + n/4 + n/8 + ..... < वास्तविक संख्या 2n => हे (एन)

Answer 2

यहाँ एक संभव दृष्टिकोण है:

• स्कैन सरणी और दुकान तत्व आवृत्तियों एक हैश तालिका में में amortized हे (एन) समय (एन विशिष्ट तत्वों के लिए लॉग इन कर रहे हैं) ; यह करने योग्य है क्योंकि we can do insertions in amortized O(1) time;
• अब इन लॉग एन तत्वों पर क्लासिक सॉर्टिंग एल्गोरिदम चलाते हैं: यह निर्धारित, हेप सॉर्ट या सॉर्ट सॉर्ट का उपयोग करके निर्धारक ओ (लॉग एन लॉग लॉग एन) समय में करने योग्य है;
• अब क्रमबद्ध सरणी का विस्तार करें --- या एक नया बनाएं और सॉर्टेड सरणी और हैश तालिका का उपयोग करके इसे भरें --- हैश तालिका से आवृत्तियों का उपयोग करके; यह ओ (एन) अमूर्त समय में करने योग्य है।

पूरे एल्गोरिदम इस प्रकार अमूर्त ओ (एन) समय में चलता है, यानी, यह डुप्लीकेट को समाप्त करने और क्रमबद्ध सरणी का विस्तार करके प्रभुत्व है। अंतरिक्ष जटिलता ओ (एन) है।

यह अनिवार्य रूप से इष्टतम है क्योंकि आपको क्रमबद्ध सरणी मुद्रित करने के लिए सभी तत्वों को "स्पर्श" करने की आवश्यकता है, जिसका अर्थ है कि हमारे पास चलने वाले समय पर ओमेगा (एन) की निचली सीमा है।

Answer 3

एक बार सरणी पर जाकर, देखा मूल्यों के लिए हैश मानचित्र रखें। जैसा कि आपने कहा था कि केवल log(n) अलग-अलग मान हैं।

अब आप सभी विभिन्न मूल्यों की सूची है - छँटाई उन्हें lon(n)*log(log(n))

ले जाएगा एक बार जब आप हल कर uniq है यह मूल सरणी constract आसान है की तरह: अधिकतम मूल्य n/2 कोशिकाओं ले जाएगा, 2 n/4 ले और इसी तरह।

कुल रन टाइम O(n + lon(n)*log(log(n)) + n) जो O(n)