题目描述

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

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

样例

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

算法1

(摩尔投票法) $O(n)$

* 此题为LeetCode.169的拓展题
* 结论：在任何数组中，出现次数大于该数组长度1/3的值最多只有两个
* 摩尔投票法其实就是抵消法，假设一个数的数量大于总数的1/3，且这个数需要用两个不同的数才能抵消。则抵消到最后这个数一定还存在
* 两个变量r1,r2作为仓库，c1,c2是仓库的计数。有两种抵消的情况
    1.r1,r2有值，且x与r1,r2不同
    2.x在某个仓库里，且新来的数与x和另外一个仓库里的数都不相同
* 如果仓库非空且新值与仓库中的值同类，则增加计数，如果仓库为空，则新添加元素进仓库；如果仓库非空，且新值与仓库里的值不同类，则开始抵消，只需要一趟遍历即可

Java 代码

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int r1 = 0, r2 = 0, c1 = 0, c2 = 0, n = nums.length;
        for(int i = 0; i < n; i++){
            int x = nums[i];
            //如果仓库中有值，需要先判断，否则无法处理所有数都相同的情况
            //前两个if和后面的if顺序不能调换
            if(c1 != 0 && x == r1){
                c1++;
            }else if(c2 != 0 && x == r2){
                c2++;
            }else if(c1 == 0){
                r1 = x;
                c1++;
            }else if(c2 == 0){
                r2 = x;
                c2++;
            }else{
                c1--;
                c2--;
            }
        }
        c1 = 0;
        c2 = 0;
        for(int i = 0; i < n; i++){
            int x = nums[i];
            if(r1 == x) c1++;
            else if(r2 == x) c2++;
        }
        if(c1 > n/3) res.add(r1);
        if(c2 > n/3) res.add(r2);
        return res;
    }
}