[algogeeks] Re: majority element

Thu, 02 Nov 2006 01:38:26 -0800

hash table :)
if u dont like O(n) space, a st.forward approach is sorting. this will take of any value of m, but ofcourse O(nlgn) time

On 11/1/06, 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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to