Leetcode: 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.

Naive Solution:
Use a hash map to contain the number of each element. Then iterate the map. 

Code (Java):

public class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        
        int len = nums.length;
        
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            int key = (int) pair.getKey();
            int value = (int) pair.getValue();
            
            if (value > len / 2) {
                return key;
            }
        }
        
        return 0;
    }
}

A constant-space solution:
Since the major element must occur more than n/2 times. We could compare each pair numbers, if not the same, we eliminate it. The left number must be the majority number. 

Code (Java):

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int result = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                result = nums[i];
                count = 1;
            } else if (nums[i] == result) {
                count++;
            } else {
                count--;
            }
        }
        
        return result;
    }
}