Majority Element

Question: 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

You may view the full question here.

Approach 1: What if we started with a simple solution? Something like this —

//Approach 1:
//Runtime: 12ms
//Memory usage: 39.1MB
class Solution {
    public int majorityElement(int[] nums) {
        int length = nums.length;
        HashMap<Integer, Integer> map = new HashMap();
        for(int n : nums){
            int count = 0;
            if(map.containsKey(n)){
                count = map.get(n);
            }
            count++;
            if(count>(length/2)){
                return n;
            }
            map.put(n, count);
        }
        return 0;
    }
}

Find more posts here.

Cheers & Chao!