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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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;     } }