I think the straightforward method it as followed:
Suppose n = 2, m = 7
Check the 2-th ,4-th,6-th elements
For general n m, there will be at most m/n such elements, by check them
one by one, u just need
O(m/n * m) time
If n = theta(m), of course, the algorithm is O(m).
Otherwise, if n m, maybe u can sort the array first then to check
directly. Just m lg(m) time.
So after merging the two algorithm, we get a
O( m * min(lg(m), m/n)) algorithm
Hope this help u.
-Original Message-
From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On
Behalf Of ericunfuk
Sent: Thursday, November 02, 2006 10:22 AM
To: Algorithm Geeks
Subject: [algogeeks] majority element
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
-~--~~~~--~~--~--~---
