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