On Mon, May 31, 2010 at 10:01 PM, souravsain <[email protected]> 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. You don't need to scan hash table again. Keep track of max while inserting. Update max when ever freq of some character is more than max. > 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 [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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
