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

解题要点：

先存到HashMap里记录个数，然后查找频率最大的数， 返回这个数的key值。

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap();
        for(int num : nums){
            if(!map.containsKey(num))
                map.put(num, 1);
            else{
                map.put(num, map.getOrDefault(num, 1) + 1);
            }  
        }

        int max = 0;
        int result = 0;
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            int key = e.getKey();
            int value = e.getValue();
            if(max < value){
                max = value;
                result = key;
            }
        }        
        return result;
    }
}

神一般的解法：

在我完成以上解法后，参照答案时发现一种新解法。虽然跟算法无关，但是神乎奇迹的逻辑让我着实很惊叹，特此记录了下来。

Algorithm

For this algorithm, we simply do exactly what is described: sort nums, and return the element in question. To see why this will always return the majority element (given that the array has one), consider the figure below (the top example is for an odd-length array and the bottom is for an even-length array):

Sorting middle index overlap

For each example, the line below the array denotes the range of indices that are covered by a majority element that happens to be the array minimum. As you might expect, the line above the array is similar, but for the case where the majority element is also the array maximum. In all other cases, this line will lie somewhere between these two, but notice that even in these two most extreme cases, they overlap at index floor(n/2) for both even- and odd-length arrays. Therefore, no matter what value the majority element has in relation to the rest of the array, returning the value at floor(n/2) will never be wrong.

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

Complexity Analysis

• Time complexity : O(nlgn)

  Sorting the array costs O(nlgn) time in Python and Java, so it dominates the overall runtime.

• Space complexity : O(1)or O(n)

  We sorted nums in place here - if that is not allowed, then we must spend linear additional space on a copy of nums and sort the copy instead.