**Presume the majority exists**, the following algo use O(1) space and
only scan the array one pass.
It is simple idea of counting. If there exists a majority elements in
the array, it must be the remaining element on the counter after we
consider all elements.
int getMajority(int A[], int n){
int count=0;
int val=0;
for (int i=1;i<n;i++){
if(count==0)
{
val=A[i];
count++;
}
else if (val==A[i])
count++;
else // val != A[i]
count--;
}
return val;
}
--~--~---------~--~----~------------~-------~--~----~
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-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
