Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than floor(n/2) times.

You may assume that the array is non-empty and the majority element always exist in the array.

Input : [2, 1, 2]
Return  : 2 which occurs 2 times which is greater than 3/2. 

Method:

Boyer–Moore majority vote algorithm

Solution:

Time: O(n)
Space: O(1)

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int majorityElement(final List<Integer> A) {
        int m = A.get(0);
        int count = 1;
        for (int i = 1; i < A.size(); i ++) {
            int val = A.get(i);
            if (val == m) {
                count ++;
            } else {
                count --;
            }
            if (count == 0) {
                m = val;
                count = 1;
            }
        }
        return m;
    }
}