Majority Element

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

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

Credits:
Special thanks to @ts for adding this problem and creating all test cases.


public class Solution {
    public int majorityElement(int[] num) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<num.length;i++) {
            int n = num[i];
            Integer count = map.get(n);
            if(count==null) {
                map.put(n, 1);
            } else {
                map.put(n, count.intValue()+1);
            }
        }
        for(Integer key : map.keySet()) {
            if(map.get(key) > num.length/2) {
                return key;
            }
        }
        return num[0];
    }
}

public class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        int threshold = nums.length / 2;
        for (int n : nums) {
            Integer f = freq.get(n);
            if (f == null) {
                freq.put(n, 1);
            } else {
                freq.put(n, f + 1);
                if (f + 1 > threshold) {
                    return n;
                }
            }
        }
        return nums[0];
    }
}

=======

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int majority = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                majority = nums[i];
                count = 1;
            } else {
                if (nums[i] == majority) {
                    count++;
                } else {
                    count--;
                }
            }
        }
        return majority;
    }
}