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