Wednesday, November 23, 2011

Majority element in an array ( Moores Voting algorithm)


public static void main(String[] args){
int a[]={2,2,3,4,2,2,1};

// Find out the candidate occurs maximum no of times
int candPos = 0,count=1;
for(int i=0;i<a.length;i++){
if(a[candPos]==a[i])
count++;
else
count--;
if(count==0){
candPos=i;
   count=1;
}
}

// now the candidate element is in position candPos
int n=0;
for(int i=0;i<a.length;i++)
if(a[candPos] == a[i])
n++;

// found out no of times candidate has occured in array
if(n > a.length/2)
System.out.println("Majority Element is : " + a[candPos]);
else
System.out.println("No majority element");

}

No comments:

Post a Comment