Majority Vote Algorithm

Question: How we can determine which element in an array is majority element? (A majority element is the one which occurs most of the time compared with the other elements)

For example in the string: ABCAGRADART - A is the majority element.

A naive solution of this problem will be to traverse the string (the array) and count the number of occurrences of every character. - In that case we will store a of of unnecessary information.

Another approach is to put every element in a hash-map and then after all the elements are in the map to traverse the elements in the map and see which has the biggest value in its key/value pair.

Both of the above solutions can be used for solving the problem but there is more effective way of doing that.

If we store a pair of the current candidate for majority element and the number of occurences. When we move through the array we compare the next element with the current one...

public class MajorityVotingAlgorithm {

public static void main(String[] args) {

char[] votes = { 'A', 'A', 'A', 'C', 'C', 'C', 'B', 'B', 'C', 'C', 'C',

'B', 'C', 'C' };

int counter = 0;

char candidate = ' ';

for (char v : votes) {

if (counter == 0) {

candidate = v;

counter++;

} else {

if (candidate == v)

counter++;

else

counter--;

}

}

System.out.println("Majority Element is: " + candidate + " (counter = "

+ counter + ")");

}

}