Solution: int majorityElement(int a[], int n) { if (a == null || a.length == 0 || n<=0) return -1; int mElement = a[0]; int count=1; for (int i=1; i < n; i++) { if (a[i] == mElement) { count++; } else { count--; } if (count <= 0) { count = 1; mElement = a[i]; } } count =0; for (int i=0; i<n; i++) { if (a[i] == mElement) { count++; } } return (count >= n/2) ? mElement : -1; }
On Thu, May 12, 2011 at 10:38 PM, pacific :-) <pacific4...@gmail.com> wrote: > a sort and another traversal would also do the same job in o( nlogn + n ) > ?? > > > On Fri, Apr 15, 2011 at 12:49 AM, vishwakarma <vishwakarma.ii...@gmail.com > > wrote: > >> complexity : O(n) + O(nlogn) >> >> Sweety wrote: >> > Question :Let A[1..n] be an array of integers. Design an efficient >> > divide and conquer algorithm to determine if A contains a majority >> > element, i.e an element appears more than n/2 times in A. What is the >> > time complexity of your algorithm? >> > >> > Answer: >> > a[1..n] is an array >> > int majorityElement(int a[], int first, int last) >> > { >> > If (first = = last) >> > { >> > return a[first]; // Array has one element and its count = >> 1 >> > and it is major element >> > } >> > mid= (first+last)/2; >> > >> > (majorL,countL)= majorityElement(a,first,mid); >> > (majorR,countR)= majorityElement(a,mid >> > +1,last); >> > n = total elements in an array; >> > If(majorL==majorR) >> > return(countL+countR); >> > else >> > { >> > If(countL>countR) >> > return(majorL,countL); >> > elseif(countL< countR) >> > return(majorR,countR); >> > else >> > return(majorL,majorR); >> > } >> > if(countL>n/2) >> > temp1=majorL; >> > if(countR>n/2) >> > temp2=majorR; >> > >> > If(temp1 = = temp2) >> > return temp1; >> > elseif(countL>countR) >> > return temp1; >> > else (countR>countL) >> > return temp2; >> > else >> > return -1; >> > } >> > >> > int main() >> > { >> > int a[8] = {2,3,2,2,4,2,2,2}; >> > int first =1; >> > int last=8; //change the value of last when the array >> > increases or decreases in size >> > int x = majorityElement(a,first,last); >> > if(x= = -1) >> > printf(“No Majority Element”) >> > else >> > Majority element = x; >> > } >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> >> > > > -- > regards, > chinna. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.