How about this?
3,3,3,3,3,3,5,5,5,5
In this case you will get the same array back and you will go into infinite loop.
Instead, you may want to keep only one of the pair if both are same, else drop both.
Even in this logic, in the worst case you may go on dropping one element from each pair at every stage and it will result in executing the algorithm for (log n) stages.
Hence the worst case complexity is O(n log n).
Another approach will be to find median in O(n) (One method is mentioned in CLR) and check whether the median occurs in the original array for more than N/2 times.
If it does, the array contains element we want, otherwise it doesn't.
~Vishal
On 6/24/06, Googmeister <
[EMAIL PROTECTED]> wrote:
subrahmanyam kambala wrote:
> HI..guys.....
> there is an element repeated more than N/2 times
>
> taking consecutive 3 elements and checking whether any two elements are
> equal or not....
But what if more than one element is repeated several times.
How will your method work?
A A A B B B B
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
