Karthik Singaram L wrote: > Hi guys, > A rather different approach to the problem > The idea is that the number is appearing more than N/2 times is > the majority. > 1. Pair the consecutive elements like 1st an 2nd element, 3rd and > 4th and so on > 2. Now if both elements in the pair are the same choose both else > drop both > 3. Repeat steps 1 and 2 till we are left with the majority element > alone > Worst case (N/2+1) is element X and (N/2-1) is element Y, this > would take nlogn.
Here's an O(n) variant. Scan through the n elements one at a time, maintaing a stack of putative majority elements as follows: * If the stack is empty, push the current element onto the stack. * If the current element is the same as the elements on the stack push another copy onto the stack. * If the current element is different from the elements on the stack delete the current element and pop one element from the stack (effectively canceling the two out). If a majority element exists, then it ends up on the stack upon termination. Use a second pass through the data to check. Note: you don't really need the stack, since it always contain some number of copies of the same element. --~--~---------~--~----~------------~-------~--~----~ 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.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---