It seems that you gotta use the "median" algrithm. Here's some idea without implementation, I wish it will help.
if the array has an odd number of lements, then the array can be devided into 3 parts: Head, Median, Tail If an element occurs more than n/m times, then at least in Head or in Tail it will occurs more than n/2m times. So we can divide and conquer it recursively. And for even case, it will be similar. On Nov 2, 10:21 am, "ericunfuk" <[EMAIL PROTECTED]> wrote: > Dear all, > > I have worked out the following algorithm for finding the majority > element(the element occurs more than n/2 times) of an array of n > elements : > > Suppose that I have a subroutine that could find the median of an array > in theta(n) time, then: > > the algorithm will be: > 1.find the median of the array > 2.check to see if it's the majority element by a single pass through > the array, and count its occurrence > > Now, what if I want to find the element that occurs more than n/m times > in the array, where m is an arbitrary integer?How can I just modify the > above to get this new algorithm?It could be very straightforward, but i > got stuck on this, > > Any hints, help appreciated!! > > Thanks. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
