I guess what guillaume said is pretty much fine and works in O(n) and as he said there is no need for stack so the algo is pretty straight assume 1st element is the majority element and set a counter to 1 compare with next element and if they are same increment counter else decrement counter if counter reaches 0 then assume next element is majority element and continue
finally whatever number is chosen may not be the majority element so once again run thro the arry and find if it occurs more than n/2 times. so O(n)!! On 6/20/06, Googmeister <[EMAIL PROTECTED]> wrote: > > > Praveen wrote: > > Hi Arun , > > > > it is not a median. it is the element which has occured > > more than N/2 time in an array. > > > > median tellls half of the element are greter then median > > value and half of the element has lesser value than median. > > If there were a majority, it would also be the median 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 -~----------~----~----~----~------~----~------~--~---
