see "median of medians" . Not straightforward, but I guess comes handy lot of places :)
On 6/20/06, Praveen <[EMAIL PROTECTED]> wrote:
Hi Arun ,
yes arun u are right it got to be a median.
so first we have to find out the median of an unsorted
array.
then we need to find whether median is occured more than
n/2 times or not.
could u just tell me how to calculate median in o(N )
time?
i feel in worst case it will take o(n^2)
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> <<a href="" [EMAIL PROTECTED]">[EMAIL PROTECTED]
> </a>> 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> Please help in solving this problem.<br><br>
> u have given an array . U need to find out the element which<br>has<br> occurred more than N/2 times where N is the array length.<br><br> for ex in an array 3,4,1,3,3,3,2,6,3 ans is 3<br> try to do it in o(N)
> <br><br> I am able to do it in O(nlogn )<br><br> my solution is first sort this array<br><br> then u would be having array like this<br><br> 1,2,3,3,3,3,3,4,6<br><br> after that u can use the following logic to find the element
> <br><br> for (int i =0;i<N/2;i++)<br> {<br> if(a[i] == a[i+N/2])<br> return a[i];<br> }<br><br> 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
-~----------~----~----~----~------~----~------~--~---
