求众数II

来源Leetcode第229题求众数II

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1:

输入: [3,2,3]
输出: [3]

---

HashMap

如果无视了题目的要求，直接无脑上HashMap，那么这题非常简单，对数组一次遍历，将其出现次数存入Map，然后在对Map做一次遍历，取出里面的众数。

public List<Integer> majorityElement(int[] nums) {
    List<Integer> ans = new ArrayList<>();
    if(nums.length == 0 || nums == null)
        return ans;
    HashMap<Integer,Integer> map = new HashMap<>();
    int times = nums.length / 3;
    for(int i = 0; i < nums.length; i++){
        if(!map.containsKey(nums[i])){
            map.put(nums[i],1);
        }else{
            map.put(nums[i],map.get(nums[i]) + 1);
        }
    }
    //Map.Entry<Integer,Integer> entry = null;
    for(Map.Entry<Integer , Integer> entry : map.entrySet()){
        if(entry.getValue() > times)
            ans.add(entry.getKey());
    }
    return ans;
}

摩尔投票法

来自网站

选票情况为：
A A A C C B B C C C B C C
结果应该是C

• 算法执行过程
  

因为可能会产生两名。所以候选人candcan**d与计数cntcnt都转成相应的数组形式candscands与cntscnt**s，长度都为2。
第一阶段成对抵销时，cands[0]与cands[1]的选票不相互抵销，即如果代表将票投给了cands[0]，则cands[1]对应的cnts[1]的值不变化。
投给cands[1]也是同样的道理。这样就转化成摩尔投票法的原始情形了。
第二阶段计数时，除了要判断两个候选的票数是否超过三分之一，还需判断两个候选是否相同。

至多选出m个代表，每个选票数大于n / (m + 1)，只需要将判断最后候选是否相同代码进行修改即可。

    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        if(nums.length == 0 || nums == null)
            return ans;

        //初始化：定义两个候选人及其对应的票数
        int candidateA = nums[0];
        int candidateB = nums[0];
        int countA = 0;
        int countB = 0;

        //遍历数组
        for (int num : nums) {
            if (num == candidateA) {
                countA++;//投A
                continue;
            }
            if (num == candidateB) {
                countB++;//投B
                continue;
            }

            //此时当前值和AB都不等，检查是否有票数减为0的情况，如果为0，则更新候选人
            if (countA == 0) {
                candidateA = num;
                countA++;
                continue;
            }
            if (countB == 0) {
                candidateB = num;
                countB++;
                continue;
            }
            //若此时两个候选人的票数都不为0，且当前元素不投AB，那么A,B对应的票数都要--;
            countA--;
            countB--;
        }

        //上一轮遍历找出了两个候选人，但是这两个候选人是否均满足票数大于N/3仍然没法确定，需要重新遍历，确定票数
        countA = 0;
        countB = 0;
        for (int num : nums) {
            if (num == candidateA)
                countA++;
            else if (num == candidateB)
                countB++;
        }
        if (countA > nums.length / 3)
            ans.add(candidateA);
        if (countB > nums.length / 3)
            ans.add(candidateB);

        return ans;
    }