This question has already been discussed here.There are 4-5 methods to do this ,best is 'Moore voting algorithm' .
refer: http://geeksforgeeks.org/?p=503 On Mon, May 31, 2010 at 10:01 PM, souravsain <souravs...@gmail.com> wrote: > Hi All > > This is my first post to this community and so am exited. The problem > is to find the no. that has maximum frequency in an array (size n) of > integers. > > The approach to use a hash table, itereate through array (O(n)) and > keep inserting into hash table (O(1)) and then scan the hash table > (O(n)) to find entry with max frequency is known. Not to mention that > one more iteration is needed to find the maximum value in array so as > to decide the sixe of hash table (to keep insertion perfectly O(N). > > I am looking for a solution which is having O(1) space complexity. The > best I can think of is to sort the array in O(nlogn) and then make a > pass through the array O(n) to find one with max frequency. So here > time complexity is O(nlogn + n). Can we have a better solution? > > -- > 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 & Regards Nikhil Agarwal Senior Undergraduate Computer Science & Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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.
