You are being specific to some programming lang. , I guess. Hashmap refers to hashing in general.
On 4/14/10, rizwan hudda <[email protected]> wrote: > O(n) is indeed the lower bound of any algorithm on this problem :) > > Yes. O(nlogn) is trivial. > > Sort the given array. > And count the number of occurrences of each element. For some element u ll > get it as 501. U have found that element! > > And about the hashmap based solution. Hashmap internally uses a tree based > structure. So, your 'n' insertion operations will indeed take O(n*logn) > time. > > I guess you meant using "Hashing technique". i,e Using a hash function to > add elements to the bucket array. And then check all the buckets with more > than 500 elements [ since there can be collisions ]. And in one of them > there will be 501 same elements. This soln is going to take O(1) expected > time. > > The open question is to look for an algorithm to find the mode in O(n) worst > case time complexity. > > > On Wed, Apr 14, 2010 at 6:33 PM, Rohit Saraf > <[email protected]>wrote: > >> O(n log n) will be trivial. >> >> O(n) is required at any cost. (Consider the case with 501 "1"s and 499 >> "0"'s) >> >> Ok, so u can make a hashmap with your integer as keys and frequency as the >> value. >> No of keys will be between 2 and 500. (=> Traversing through takes >> O(n) ) >> You will have to traverse the array exactly once => O(n) >> => O(n) solution. >> >> And it cannot be made better ! >> >> -------------------------------------------------- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> >> >> On Wed, Apr 14, 2010 at 4:14 PM, Gauri <[email protected]> wrote: >> >>> Say If I have an array of 1,000 32-bit integers .And one of the value >>> is occuring 501 number of times or more in the array. Can someone help >>> me devise an efficient algorithm for the same ? >>> >>> Thanks & Regards >>> Gauri >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Thanks and regards > Rizwan A Hudda > http://sites.google.com/site/rizwanhudda > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Sent from my mobile device -------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
