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.

Solution1: hashmap

Use a hashmap to store element and the times it appears. Key is element, value is the times it appears. 

Store into hashmap is O(n), look for the majority element is O(n). So run time complexity is O(2n) = O(n). Space complexity is O(n).

public class Solution {
    public int majorityElement(int[] num) {
        HashMap map = new HashMap();
        for(int n : num) {
            if(map.containsKey(n)) {
                map.put(n, map.get(n) + 1);
            }else {
                map.put(n, 1);
            }
        }
        
        for(int element : map.keySet()) {
            if(map.get(element) > num.length / 2) {
                return element;
            }
        }
        
        return -1;
    }
}

Solution2: optimize the space complexity to constant space.
Sort the array first, since majority element appears more than n/2 times. So the n/2 element in the array must be the majority element. We just need to return the middle element.
Sort array takes O(nlogn), so run time complexity is O(nlogn), constant space.

public class Solution {
    public int majorityElement(int[] num) {
        Arrays.sort(num);
        return num[num.length / 2];
    }
}