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 <pre.la...@gmail.com> 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.