A Linear Time Majority Vote Algorithm:
Traverse the array starting from the first index.
As we traverse we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.
When we move the pointer forward over an element X:
If the counter is 0, we set the current candidate to X and we set the counter to 1.
If the counter is not 0, we increment or decrement the counter according to whether X is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.
Input:
char [] arr = {'A', 'A', 'A', 'C', 'C', 'B', 'B', 'C', 'C', 'C', 'B', 'C', 'C'};
Output:
Majority Element: C
Traverse the array starting from the first index.
As we traverse we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.
When we move the pointer forward over an element X:
If the counter is 0, we set the current candidate to X and we set the counter to 1.
If the counter is not 0, we increment or decrement the counter according to whether X is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.
Input:
char [] arr = {'A', 'A', 'A', 'C', 'C', 'B', 'B', 'C', 'C', 'C', 'B', 'C', 'C'};
Output:
Majority Element: C
Solution fails in
ReplyDeletechar [] arr = {'A', 'B', 'C', 'A', 'E'};
producing output as E