डाटा संरचनाओं सवाल

Question

यह सवाल एक परीक्षा मैं था से है, और मैं इसे हल नहीं कर सकता है और देखने के लिए क्या जवाब है चाहता था (यह, होमवर्क नहीं है, क्योंकि यह मुझे कुछ भी लेकिन ज्ञान में मदद नहीं करेगा)।

हमें उन तत्वों के लिए डेटा संरचना बनाने की आवश्यकता है जिनकी कुंजी वास्तविक संख्याएं हैं।
डेटा संरचना में ये कार्य होना चाहिए:
बिल्ड (एस, सरणी): ओ (एन)
में एन तत्वों के साथ डेटा संरचना एस बनाता है ओ में सम्मिलित करें (एस, के) और हटाएं (एस, एक्स) lgn) (k एक तत्व है, x डेटा संरचना में इसके लिए एक सूचक है)
हटाएं-न्यूनतम-सकारात्मक (एस): न्यूनतम सकारात्मक कुंजी
मोड (एस) के साथ तत्व निकालें: कुंजी हे में एस में सबसे लगातार (1)

अब, हे में निर्माण (एन) आमतौर पर एक ढेर इस्तेमाल किया जाना चाहिए मतलब है, लेकिन यह है कि आवृत्तियों को खोजने के लिए अनुमति नहीं है। मुझे ऐसा करने का कोई रास्ता नहीं मिला। सबसे अच्छा मैं एक रेड-ब्लैक-ट्री (ओ (nlgn)) का निर्माण कर रहा हूं जिसका उपयोग आवृत्ति ढेर बनाने के लिए किया जाएगा।

मैं जवाब जानने के मर रहा हूँ ...

धन्यवाद!

Answer 1

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

जब आप एक कुंजी डालने या एक महत्वपूर्ण हटाते हैं, तो आप को बढ़ा या एक के बाद घटनाओं क्षेत्र की संख्या घटती, या गंभीर मामलों में जोड़ने के लिए या एक ढेर तत्व को हटा दें। दोनों मामलों में आपको ऊपर/नीचे घूमने की आवश्यकता है क्योंकि ऑर्डरिंग फ़ील्ड बदल गया है।

हैश तालिका मान लिया जाये कि हे (1) ऑपरेशन है, आप एक मानक ढेर + O (1) हैश तालिका है और आप समय सीमा के भीतर ऊपर सभी कार्यों मिलता है। विशेष रूप से, आपको ढेर के मूल तत्व को पढ़कर "मोड" मिलता है।

Answer 2

मुझे लगता है कि निम्नलिखित समाधान स्वीकार्य होगा। यह दो डेटा stuctures के आधार पर:

1. लाल काला पेड़
2. द्विआधारी ढेर

द्विआधारी ढेर टपल, जिनमें शामिल है रखती है (तत्व मूल्य, तत्व की बारंबारता), ढेर आवृत्तियों पर builded है, तो यह हमें ओ (1) में मोड खोजने की क्षमता देता है।

लाल काला पेड़ (ढेर में एक ही तत्व मूल्य के तत्व मूल्य, सूचक) एक टपल कि पकड़

जब आप नए तत्व डालने की आवश्यकता है, तो आप तत्व की तलाश करेगा (यह हे लेता शामिल (लॉग एन)), यदि खोज सफल रही, आरबी-पेड़ में स्थापित तत्व से पॉइंटर पर जाने, आवृत्ति में वृद्धि, और ढेर पुनर्निर्माण (ओ ओ (लॉग एन))। यदि खोज को आरबी-पेड़ (ओ (लॉग एन) में डालने से अधिक तत्व नहीं मिला है और मान = (तत्व, 1) (ओ ओ (1)) के साथ ढेर करने के लिए, आरबी-पेड़ में एक पॉइंटर सेट करें ढेर में तत्व। क्योंकि n तत्व के सेट से दोनों संरचनाओं के निर्माण

प्रारंभिक निर्माण, हे (एन) ले जाएगा हे (एन) लेता है।

क्षमा करें, अगर मुझे कुछ याद आ रहा है।

Answer 3

केवल तुलना मॉडल का उपयोग कर, इस समस्या के लिए कोई समाधान है।

Element Distinctness Problem साध्य ओमेगा (nlogn) निचले सीमा है। यह (तत्व विशिष्टता) समस्या मूल रूप से यह निर्धारित करने की समस्या है कि किसी सरणी के सभी तत्व अलग हैं या नहीं।

यदि आपकी समस्या का कोई समाधान था, तो हम ओ (एन) समय में तत्व विशिष्टता समस्या का उत्तर दे सकते हैं (ओ (एन) समय में सबसे अधिक बार तत्व ढूंढें, और देखें कि क्या एक से अधिक उदाहरण हैं वह तत्व, फिर ओ (एन) समय में)।

तो, मैं सुझाव है कि आप कम्प्यूटेशनल मॉडल के लिए अपने प्रोफेसर पूछना।

Answer 4

आवृत्तियों के लिए:
प्रत्येक प्रविष्टि द्वि-directionaly खुद आवृत्तियों/काउंटरों (उपयोग हैश तालिका) से जुड़ा हुआ
आवृत्ति लिंक्ड सूची में हो रहा है।
लिंक की गई सूची पर आवृत्ति ऊपर/नीचे स्थानांतरित करने की आवश्यकता है, (डालने वाला तत्व हटाया जा रहा है) लेकिन अधिकतम अंतर के लिए 1.

फ़्रीक्वेंसी इस प्रकार +1 और -1 आवृत्ति तत्व के सूचक से जुड़ी हुई है।

(अपवाद हैं लेकिन इसे संभाला जा सकता है)