Majority Elements

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.

---

用hashtable解法复杂度是O(n),空间复杂度也是O(n)，但是根据题目，majority element出现了 more than n/2 次，应该有更快的解法。需要再想想。
Solution 1:

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

Solution 2:
非常elegant的解法，参见Moore’s Voting Algorithm

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