LeetCode刷题实战229：求众数 II-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 求众数 II，我们先来看题面：

https://leetcode-cn.com/problems/majority-element-ii/

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Follow-up: Could you solve the problem in linear time and in O(1) space?

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

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

示例

示例 1：

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

示例 2：

输入：nums = [1]
输出：[1]

示例 3：

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

解题

https://www.acwing.com/solution/content/19400/

此题为LeetCode.169的拓展题

结论：在任何数组中，出现次数大于该数组长度1/3的值最多只有两个

摩尔投票法其实就是抵消法，假设一个数的数量大于总数的1/3，且这个数需要用两个不同的数才能抵消。则抵消到最后这个数一定还存在

两个变量r1,r2作为仓库，c1,c2是仓库的计数。有两种抵消的情况

1. r1,r2有值，且x与r1,r2不同

2 .x在某个仓库里，且新来的数与x和另外一个仓库里的数都不相同

如果仓库非空且新值与仓库中的值同类，则增加计数，如果仓库为空，则新添加元素进仓库；如果仓库非空，且新值与仓库里的值不同类，则开始抵消，只需要一趟遍历即可

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;
    }
}