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: [email protected] [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 [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 -~----------~----~----~----~------~----~------~--~---
