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 <dave_and_da...@juno.com> 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 <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<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 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.