solution in o(n log n)
can be ( as if solution exit only one element cam be a majority element in
the given array)
1. sort the array in O(nlogn)
2. x = a[2n/3]
if(a[0]==x)
{ if(x== a[(2n/3])+1)
return (x)
}
On Wed, Sep 22, 2010 at 5:53 AM, Dave <[email protected]> wrote:
> Try something like this:
>
> int FindMajority( int n , int a[] )
> {
> int majority = a[0];
> int count = 1;
> for( i = 1 ; i < n ; ++i )
> {
> if( a[i] == majority )
> {
> ++count;
> }
> else
> {
> if( count == 0 )
> {
> majority = a[i];
> count = 1;
> }
> else
> {
> --count;
> }
> }
> }
> return majority;
> }
>
> It will find an element that occurs at least n/2 times in the array.
> If you need to verify that the element occurs 2n/3 times, add a loop
> to count the number of occurences of majority before the return.
>
> On Sep 21, 10:42 pm, pre <[email protected]> wrote:
> > Hi all,
> > pls help me solve this problem..
> > Design an algorithm to find the majority element of an array..
> > majority element must be an element tht has the cardinality greater
> > than 2n/3 where n is the number of elements in the array and the time
> > complexity must be a linear time.. ie o(n)..
> >
> > hint : use mode or median to solve ..
>
> --
> 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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
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?hl=en.
