सरणी में एन वें सबसे लगातार संख्या का पता लगाएं

Question

Find the nth most frequent number in array. 
(There is no limit on the range of the numbers) 

मुझे लगता है कि हम कर सकते हैं

(i) सी में नक्शे का उपयोग ++ हर तत्व की घटना की दुकान

(ii) अधिकतम ढेर का निर्माण तत्व के अवसर (या आवृत्ति) के रैखिक समय में और फिर एन-वें तत्व तक निकालें, प्रत्येक निकासी को हेपफाइफ़ करने के लिए लॉग (एन) समय लगता है।

(iii) हम एन वें सबसे अक्सर संख्या की आवृत्ति मिल जाएगा

(iv) तो हम तत्व इस आवृत्ति वाले को खोजने के लिए कर सकते हैं रैखिक हैश के माध्यम से खोज।

समय - ओ (NlogN) स्पेस - हे (एन)

कोई बेहतर तरीका है?

Answer 1

आपकी विधि मूल रूप से सही है। यदि आप निर्मित ढेर के प्रत्येक वर्टेक्स को उस संख्या के साथ चिह्नित करते हैं, तो आप अंतिम हैश खोज से बचेंगे। इसके अलावा, ढेर के पांचवें तत्व को लगातार बनाए रखना संभव है क्योंकि आप इसे बना रहे हैं, क्योंकि किसी बिंदु पर आप ऐसी परिस्थिति में जा सकते हैं जहां नतीजा अब और नहीं बदला जा सकता है और शेष गणना को हटाया जा सकता है। लेकिन यह संभवतः सामान्य मामले में एल्गोरिदम तेजी से नहीं बना सकता है, और शायद विशेष मामलों में भी नहीं। तो आपने अपने प्रश्न का सही उत्तर दिया।

Answer 2

यह इस बात पर निर्भर करता है कि आप सबसे प्रभावी, या सबसे आसान लिखने की विधि चाहते हैं या नहीं।

1) यदि आप जानते हैं कि सभी संख्याएं 0 से 1000 तक होंगी, तो आप केवल 1000 शून्य (मौके), सरणी को अपनी सरणी के माध्यम से लूप करें और सही मौके की स्थिति में वृद्धि करें। फिर आप इन अवसरों को सॉर्ट करते हैं और एनएच मान का चयन करते हैं।

2) आपके पास अद्वितीय वस्तुओं का "बैग" है, आप अपनी संख्याओं के माध्यम से लूप करते हैं, जांचें कि क्या यह संख्या बैग में है, अगर नहीं, तो आप इसे जोड़ते हैं, अगर यह यहां है, तो आप केवल अवसरों की संख्या में वृद्धि करते हैं । फिर आप इससे एनएचटी सबसे छोटी संख्या चुनते हैं।

बैग रैखिक सरणी, बीएसटी या शब्दकोश (हैश तालिका) हो सकता है।

सवाल यह है कि "एन वें सबसे अक्सर", इसलिए मुझे लगता है कि आप छँटाई (या चतुर डेटा संरचना) से बचने नहीं कर सकते हैं, तो सबसे अच्छा जटिलता नहीं बेहतर हो सकता है हे की तुलना में (एन * लॉग (एन))।

Answer 3

यह रैखिक समय और स्थान में किया जा सकता है। इनपुट इनपुट सरणी में तत्वों की कुल संख्या होने दें, जिससे हमें एनएच सबसे अधिक संख्या मिलती है:

1. मानचित्र में टी में प्रत्येक संख्या की आवृत्ति को गणना और संग्रहित करें। एम को सरणी में विशिष्ट तत्वों की कुल संख्या होने दें। तो, मानचित्र का आकार एम है - ओ (टी)
2. Selection algorithm का उपयोग करके मानचित्र में एनएचटी सबसे बड़ी आवृत्ति पाएं। - हे (एम)

कुल समय = हे (टी) + O (एम) = हे (टी)