Sorry i meant This soln is going to take O(n) expected time.
and not This soln is going to take O(1) expected time. On Wed, Apr 14, 2010 at 6:43 PM, rizwan hudda <rizwanhu...@gmail.com> 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 > <rohit.kumar.sa...@gmail.com>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 <gauri...@gmail.com> 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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> 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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> 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 > > > > -- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
