public class Solution {
    public int majorityElement(int[] num) {
        int n = num.length;
        HashMap<Integer, Integer> hsMap = new HashMap<Integer, Integer>();

        for (int i = 0; i < n; i++) {
            if (hsMap.get(num[i]) == null) {
                hsMap.put(num[i], 1);

                if (1 > (n / 2)) {
                    return num[i];
                }
            } else // hsMap.get(num[i]) != null
             {
                if ((hsMap.get(num[i]) + 1) > (n / 2)) {
                    return num[i];
                }

                hsMap.put(num[i], hsMap.get(num[i]) + 1);
            }
        }

        return -1;
    }
}