Hi Amit ,
Creating a binary tree for n element takes o(nlogn) not
o(logn).
we can understand it by one examples
lets have an array 1,2,3 ,4 ,5 ,6,7,8 try to create the binary
tree
it required more than 8 comparison
it is a nothing but a sorting. after putting element in binary
tree if we traverse
the tree inorder we will get the element in ascending order.
I feel your algo also takes nlogn times.
Regards
Praveen
Amit Banwari wrote:
> Hi Praveen.
>
> May be this can help u.
>
> Create a Binary tree with array[N/2] as the root.
>
> Have every node in the tree be composed of { value and no of times }
> where value is the value of the array element and the no of times
> denotes the number of
> occurrences.
>
> Visit each node one by one and all nodes left to ROOT are less than
> root and all
> nodes greater are to the right of ROOT.
>
> If a value is repeated u will reach there again and again and increment it.
> After incrementing just check if it is greater than N/2
> If yes you have the value, if no carry on.
>
> **adding n elements in a binary tree is O(log n)
>
> Thanks
> amit
>
>
> On 6/20/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
> >
> >
> > >
> >
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
