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

[Praveen]

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.
Regards
Praveen

Arun wrote:

> looks like the number will be median which we can find find in linear time.
>
> On 6/19/06, Praveen <[EMAIL PROTECTED]> wrote:
> >
> >
> > Hi guys,
> >
> >          Please help in solving this problem.
> >
> >         u have given an array . U need to find out the element which
> > has
> >         occurred more than N/2 times where N is the array length.
> >
> >         for ex  in an array 3,4,1,3,3,3,2,6,3   ans is 3
> >        try to do it in o(N)
> >
> >         I am able to do it in O(nlogn )
> >
> >         my solution is first sort this array
> >
> >          then u would be having array like this
> >
> >             1,2,3,3,3,3,3,4,6
> >
> >         after that u can use the following logic to find the element
> >
> >        for (int i =0;i<N/2;i++)
> >        {
> >               if(a[i] == a[i+N/2])
> >                    return a[i];
> >          }
> >
> >         is there any better method for this.
> >
> > Regards
> > Praveen
> >
> >
> > >
> >
>
> ------=_Part_3114_7085459.1150786948554
> Content-Type: text/html; charset=ISO-8859-1
> X-Google-AttachSize: 1929
>
> looks like the number will be median which we can find find in linear 
> time.<br><br><div><span class="gmail_quote">On 6/19/06, <b 
> class="gmail_sendername">Praveen</b> &lt;<a href="mailto:[EMAIL 
> PROTECTED]">[EMAIL PROTECTED]
> </a>&gt; wrote:</span><blockquote class="gmail_quote" style="border-left: 1px 
> solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 
> 1ex;"><br>Hi guys,<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
> Please help in solving this problem.<br><br>
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u have given an array . U 
> need to find out the element 
> which<br>has<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;occurred more 
> than N/2 times where N is the array 
> length.<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for 
> ex&nbsp;&nbsp;in an array 3,4,1,3,3,3,2,6,3&nbsp;&nbsp; ans is 
> 3<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; try to do it in o(N)
> <br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;I am able to do it in 
> O(nlogn )<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;my solution 
> is first sort this 
> array<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; then u would be 
> having array like 
> this<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1,2,3,3,3,3,3,4,6<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;after
>  that u can use the following logic to find the element
> <br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (int i 
> =0;i&lt;N/2;i++)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
> {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(a[i]
>  == 
> a[i+N/2])<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
>  return a[i];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
> }<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;is there any better 
> method for this.<br><br>Regards<br>Praveen<br>
> <br><br>
> ------=_Part_3114_7085459.1150786948554--


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