पुस्तक "एल्गोरिथ्म डिजाइन मैनुअल" Skiena द्वारा में, कंप्यूटिंग एक सेट के मोड (सबसे लगातार तत्व), एक Ω कहा जाता है कि (n लॉग n) लोअर बाउंड (इस पहेली मुझे) , लेकिन यह भी (सही ढंग से मुझे लगता है) कि मोड की गणना के लिए कोई तेज़ सबसे खराब केस एल्गोरिदम मौजूद नहीं है। मैं केवल निचले बाध्य होने से परेशान हूं Ω (एन लॉग एन)।रैखिक समय में एक सेट के मोड (सबसे लगातार तत्व) की गणना?
पर पुस्तक के पृष्ठ देखें लेकिन निश्चित रूप से यह कुछ मामलों में रेखीय समय (सबसे अच्छा मामले), उदा में परिकलित किया जा सकता जावा कोड द्वारा नीचे की तरह (एक स्ट्रिंग में सबसे लगातार चरित्र पाता है), "चाल" हैशटेबल का उपयोग करके अवसरों की गणना करने के लिए। यह स्पष्ट प्रतीत होता है।
तो, समस्या की मेरी समझ में मुझे क्या याद आ रही है?
संपादित करें: (रहस्य हल) StriplingWarrior बताते हैं के रूप में, निम्न बाउंड धारण करता है, तो केवल तुलना उपयोग किया जाता है, यानी स्मृति का कोई अनुक्रमण, यह भी देखें: http://en.wikipedia.org/wiki/Element_distinctness_problem
// Linear time
char computeMode(String input) {
// initialize currentMode to first char
char[] chars = input.toCharArray();
char currentMode = chars[0];
int currentModeCount = 0;
HashMap<Character, Integer> counts = new HashMap<Character, Integer>();
for(char character : chars) {
int count = putget(counts, character); // occurences so far
// test whether character should be the new currentMode
if(count > currentModeCount) {
currentMode = character;
currentModeCount = count; // also save the count
}
}
return currentMode;
}
// Constant time
int putget(HashMap<Character, Integer> map, char character) {
if(!map.containsKey(character)) {
// if character not seen before, initialize to zero
map.put(character, 0);
}
// increment
int newValue = map.get(character) + 1;
map.put(character, newValue);
return newValue;
}
इरेटा सूची में कुछ भी उल्लेख नहीं किया गया है: http://www.cs.sunysb.edu/~skiena/algorist/book/errata –
पृष्ठ को पढ़ नहीं सकता है। स्पष्ट रूप से डैनिश, कुछ अपमानजनक संदेश। –
google.dk को google.com पर बदलें, और यह काम करेगा। – StriplingWarrior