[algogeeks] Re: find the most occured (more than N/2 times , where N is the length of the array) element in an array

Tue, 20 Jun 2006 10:17:07 -0700

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
-~----------~----~----~----~------~----~------~--~---

Reply via email to