Majority Element II

Majority Element II
给定一个长度为n的数组，找出所有出现次数大于[n/3]的元素。

这道题是Majority Element的变形，如果次数大于[n/2]时，只可能有一个元素，这里要求出现次数多于[n/3]次，也就是说有可能有两个元素，同样我们可以用哈希表来做，这样时间复杂度为O(n)，空间复杂度为O(n)。代码如下：

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        List<Integer> list = new ArrayList<Integer>();
        if(nums == null || nums.length == 0) return list;
        for(int i = 0; i < nums.length; i++) {
            if(hm.containsKey(nums[i])) {
               hm.put(nums[i],hm.get(nums[i]) + 1);
            } else {
                hm.put(nums[i], 1);
            }
            if(hm.get(nums[i]) > (nums.length / 3) && !list.contains(nums[i]))
                    list.add(nums[i]);
        }
        return list;
    }
}

用哈希来做勉强可以通过测试，我们也可以用Moore‘s voting算法，与上一题不同的是这里需要两个带比较的元素，因为结果可能有两个，我们遍历完之后，还需要再遍历一遍数组，确定是否它们的出现次数大于[n/3]。这样时间复杂度为O(n)，空间复杂度为O(1)，代码如下：

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        if(nums == null || nums.length == 0) return list;
        int result1 = 0;
        int result2 = 0;
        int count1 = 0;
        int count2 = 0;
        
        for(int i = 0; i < nums.length; i++) {
            if(count1 == 0 && nums[i] != result2) {
                result1 = nums[i];
            } else if(count2 == 0 && nums[i] != result1) {
                result2 = nums[i];
            }
            if(nums[i] == result1) {
                count1 ++;
            } else if(nums[i] == result2) {
                count2 ++;
            } else {
                count1 --;
                count2 --;
            }
        }
        count1 = 0;
        count2 = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == result1) count1 ++;
            if(nums[i] == result2) count2 ++;
        }
        if(count1 > nums.length / 3) list.add(result1);
        if(count2 > nums.length / 3 && !list.contains(result2)) list.add(result2);
        return list;
    }
}