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 :-) <[email protected]> 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 <[email protected]
> > 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 [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.
>>
>>
>
>
> --
> 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 [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.
>
--
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.
