169. Majority Element - jiejackyzhang/leetcode-note GitHub Wiki

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.

Array类题目。

##Approach 1: sort 由于majority element始终存在，它的出现次数又大于⌊ n/2 ⌋次，因此若将数组排序，则中间位置的数必然是majority element。

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

##Approach 2: hash map

public class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int num : nums) {
            map.put(num, map.containsKey(num)? map.get(num)+1 : 1);
            if(map.get(num) > nums.length/2) return num;
        }
        return 0;
    }
}