169. 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.

Example 1:

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

Example 2:

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

解析：这道题目的前提是给的数组里肯定有一个数字，它的数量大于n/2。看到这个题目让我想到之前two sum，可以用hashMap来保存数字对应的数量，然后一遍历就ojbk了，而且时间复杂度是o(n)，下面上解法：

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
        for(int n : nums){
            if(countMap.containsKey(n)){
                Integer count = countMap.get(n);
                count++;
                countMap.put(n, count);
            }else{
                countMap.put(n, 1);
            }
        }
        int medium = nums.length / 2;
        for(Map.Entry<Integer, Integer> entry : countMap.entrySet()){
            if(entry.getValue() > medium){
                return entry.getKey();
            }
        }
        return -1;
    }
}

submit后，只超过了32.11%的java版本。。。

Runtime: 15 ms, faster than 32.11% of Java online submissions for Majority Element.

Memory Usage: 44.1 MB, less than 5.11% of Java online submissions for Majority Element.

看了一下别人的解答，还有三四种高端解法，这里列出一个比较大跌眼镜的解法,原理是如果有一个数字的数量超过了n/2，那么中位数肯定就是要找的那个数字：

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