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.

Example 1:
Input: [3,2,3]
Output: 3

Solution

1. Hash map
   Time O(N)
   Space O(N)

class Solution {
    public int majorityElement(int[] nums) {
        int max=0;
        int major=0;
        Map<Integer,Integer> map= new HashMap<Integer,Integer>();
        for(int k: nums){
            if(map.containsKey(k)){
                map.put(k,map.get(k)+1);
                    
            }
            else
                map.put(k,1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(max<entry.getValue()){
                max=entry.getValue();
                major=entry.getKey();
            }
    }
        return major;
    }
}

2. Sort
   个数大于N/2则sort后去中间即可（始终保证为mojor）
   Time O(NlogN)
   Space O(1)

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