Majority Element

• HashMap记录次数，然后在看是否超过n/2
• sorting, 这样majority element一定会在n/2处

Majority Element II

• 利用上一题的思路。可以知道，每次消去三个不同的元素。最后留下来的元素就必定存在（但不全是）出现超过[n/3]次的元素。
• 问题就在于如何在O(1)的space要求下，完成『消去』操作。引入两个num和count，每次比较元素当遇到相同的则增加count，反之减少。当count为0的时候，更新num
• 要注意，最后留下来的元素不一定全是满足要求的，同时count的值也不是真正的freq，所以需要重新计算count值，而后决定是否要加入

public List<Integer> majorityElement(int[] nums) {
        // find the a pair of 3 nums, remove them from the nums; the remainings are the res        
        List<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) 
            return ans;

        //how to "remove" from the nums
        int num1 = 0;
        int num2 = 0;
        int count1 = 0;
        int count2 = 0;

        for (int num : nums) {
            if (num == num1) {
                count1++;
            } else if (num == num2) {
                count2++;
            } else if (count1 == 0) {
                num1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                num2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }           
        }
        //until here, it finds the number left, but the count is not the freq
        count1 = 0;
        count2 = 0;

        for (int num: nums) {
            if (num == num1)
                count1++;
            else if (num == num2)
                count2++;
        }

        if (count1 > nums.length / 3)
            ans.add(num1);
        if (count2 > nums.length / 3)
            ans.add(num2);

        return ans;
    }