题目描述

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

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

样例

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

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

算法分析

摩尔投票法 (leetcode上的题解 + 自己的理解)

做这个题之前可以先看一下169题，投票算法，169题，找一个众数，那就只要一个候选，他是保证一定有一个是众数的，直接投票就好
但是这个题没有保证有一个元素一定出现 n/3以上。

首先我们得明确，n/k的众数最多只有k - 1个，为什么呢？假设有k个众数，n/k * k = n,这k个元素都是众数，还要不同，怎么可能啊。那么对于这个题，超过n/3的数最多只能有3 - 1 = 2 个，我们可以先选出两个候选人A,B。

• 1.如果投A（当前元素等于A），则A的票数++;

• 2.如果投B（当前元素等于B），B的票数++;

• 3.如果A,B都不投（即当前与A，B都不相等）,那么检查此时A或B的票数是否减为0：

  • 3.1 如果为0,则当前元素成为新的候选人；

  • 3.2 如果A,B两个人的票数都不为0，那么A,B两个候选人的票数均减一；

最后会有这么几种可能：有2个大于n/3，有1个大于n/3，有0个大于n/3，遍历结束后选出了两个候选人，但是这两个候选人是否满足> n/3，还需要再遍历一遍数组，找出两个候选人的具体票数，因为题目没有像169题保证一定有。

自己的见解

如果存在一个数出现次数 > n/3，那么这个数一定会在A和B候选人之中。

证明：假设存在一个数出现次数 > n / 3，设这个数是A，当它一开始在候选人A时，才会被消耗次数最多，又由于B候选人又存放着其他元素，因此必须至少需要有 > n / 3个不同于A、B的元素才能把A中的元素消耗掉，消耗A的同时也在消耗B，消耗B中的元素也至少有 > n / 3个，（即使B候选人换了人也无所谓，使用到不同的数只会多不会少，因为消耗完B后，需要另一个不同的元素补进B候选人中，还需要另外增加不同的元素，然而却没有消耗掉A），因此需要把A全部消耗完，至少需要消耗 > n / 3 个不同的元素，以及至少需要消耗 B 候选人 > n / 3个次数，又因为A这个数本身的次数就 > n / 3，消耗的总数 + 自己的次数 一定 > n，因此矛盾，所以一个数出现次数 > n / 3，按照这样的方式，一定不会消耗完，则一定会在A和B候选人中

时间复杂度 $O(n)$

Java 代码

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        int n = nums.length;
        int r1 = 0, r2 = 0, c1 = 0, c2 = 0;
        for(int i = 0;i < n;i ++)
        {
            if(c1 != 0 && nums[i] == r1) c1 ++;
            else if(c2 != 0 && nums[i] == r2) c2 ++;
            else if(c1 == 0) 
            {
                r1 = nums[i];
                c1 ++;
            }
            else if(c2 == 0)
            {
                r2 = nums[i];
                c2 ++;
            }
            else 
            {
                c1 --;
                c2 --;
            }
        }
        c1 = 0;
        c2 = 0;
        for(int i = 0;i < n;i ++)
        {
            if(nums[i] == r1) c1 ++;
            else if(nums[i] == r2) c2 ++;
        }
        if(c1 > n / 3) res.add(r1);
        if(c2 > n / 3) res.add(r2);
        return res; 
    }
}