Please read the question properly...The number can be a majority element only if it repeats more than n/2 times....In your example it doesnt...
On 6/20/06, Vikram Venkatesan <[EMAIL PROTECTED]> wrote: > Hi, > > The problem with that PAIRING solution is that, at each step, some > information is lost.... > Say, the array is 2,5,2,7,2,8,2,1 > While taking elements pair by pair, first, since 2 !=5 , we skip it... (At > this step itself, the information about the occurence of '2' is lost).... > The same happens in the further steps too... Finally, we end up with a 'NO > SUCH NUMBER' answer for this array, which is not the expected ans.... > > Vikram > > > On 6/20/06, Pradeep Muthukrishnan <[EMAIL PROTECTED]> wrote: > > > > 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 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 -~----------~----~----~----~------~----~------~--~---
