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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
