题目

the leetcode link

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

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

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

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

提示：
1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

摩尔投票法

解题思路

我从设计一个游戏入手，为你讲解摩尔投票的思路。

设计一款类似俄罗斯方块的简单消除游戏

游戏主板块是三个纵向列队槽组成的无上限空间，如图。设计一下落方块数组，比如 [A,A,A,B,B,C]，一个方块能占一个槽位。

元素方块按数组顺序轮流出现，落入板块中。你将左右移动操作下落中的方块，直到下降至其中一个槽位，完成方块堆叠。（其实就是俄罗斯方块的玩法）

1
2
3
4
5
6
|口口口|    <--方块从上向下堆叠
|口口口|
|口口口|      
|口口口|       
|口口口|    <--"口"是槽位，有三列           
--------

我们的规则是：当一层填满，且元素均不相同，该层立马发生消除。消除后剩余方块最少则胜利。

1
2
3
4
5
6
|口口口|        |口口口|
|口口口|  ==>   |口口口|
|A 口口|        |口口口|
|A B 口|        |A 口口|
|A̶ ̶B̶ ̶C̶ | 消除   |A B 口|  ↓
--------        --------

根据规则，一旦同一层出现相同元素，则无法消除，因此我们要保证同一层均不相同，采取攻略：遇到相同元素叠在一起，遇到不同元素则放在其他槽位，最后使一层填满并完成消除。这样会发现，底层总是在消除，所以必定会有一列是空队槽。

试一局就清楚了，数组：[A,B,C,A,B,C,A,B,C,A,A,B]
A,B,C 不相同，各放在不同槽位，一层满则消除，此时面板存储为空
A,B,C 不相同，各放在不同槽位，一层满则消除，此时面板存储为空
A,B,C 不相同，各放在不同槽位，一层满则消除，此时面板存储为空
A,A 相同，堆叠在左边槽位，此时面板左边存储了AA
B 与A不相同，放在不同槽位，此时面板左边存储了AA，中间存储B

1
2
3
4
5
6
|A 口口|        |口口口|
|A B 口|  ==>   |口口口|
|A̶̶̶ ̶B̶ ̶C̶ |        |口口口|
|A̶̶̶ ̶B̶ ̶C̶ |        |A 口口|
|A̶̶̶ ̶B̶ ̶C̶ | 消除   |A B 口|  ↓
--------        --------

按照图中堆叠，抵消后剩下结果A B，由于数组只有ABC三种元素，那么剩下结果都是个数超过N/3的元素。

再试一局，数组：[X,Y,B,Q,R,T,A,A,B,C,A,B]
X,Y,B 不相同，各放在不同槽位，一层满则消除，此时面板存储为空
Q,R,T 不相同，各放在不同槽位，一层满则消除，此时面板存储为空
A,A 相同，堆叠在左边槽位，此时面板左边存储了AA
B 与A不相同，放在不同槽位，此时面板左边存储了AA，中间存储B
C 与A，B不相同，放在不同槽位，A,B,C一层满消除，，此时面板左边存储了AA，中间存储B

1
2
3
4
5
6
|A 口口|        |口口口|
|A B 口|  ==>   |口口口|
|A̶̶̶ ̶B̶ ̶C̶ |        |口口口|
|̶Q̶ ̶R̶ ̶T̶ |        |A 口口|
|̶X̶ ̶Y̶ ̶B̶ ̶| 消除   |A B 口|  ↓
--------        --------

按照图中堆叠，抵消后剩下结果A B，由于数组本身没有个数超过N/3的元素，说明剩下的元素也没有个数超过N/3的。

就是说，在每遇3个不同元素就互相抵消的玩法下，如果存在数量超过N/3的元素，抵消后一定有此元素的剩余；但剩余的，不一定都是数量超过N/3的元素。

所以，我们只需要取得消除后剩余的元素，通过遍历数组对其计数，判断个数是否满足大于N/3即可得到本题的答案

游戏替换成摩尔投票

每次元素方块下落，就相当于对其元素的一次投票。
当一层的每个槽位（候选人）都有一票，因为这些票不影响最终结果，互相进行抵消。
被投票个数超过N/3一定会留到最后不被消除。

代码思路

  1. 初始化两个槽位以及其存储元素个数。
    （为什么不定义三个槽位？ 有一个槽位必然用于抵消掉其他槽位，存储元素必是0，只需关注其他槽位存储情况即可）
  2. 优先进槽位1，当前元素与槽位1相同元素则堆叠，不符合则入槽位2
  3. 入槽位2时，当前元素与槽位2相同元素则堆叠；不符合则入空队槽
  4. 优先入空槽1，否则空槽2，否则入剩余槽
  5. 入剩余槽时，会与其他槽发生一次抵消，此槽又变回空槽
  6. 最后获得剩下在队槽的元素，并数出对应元素在数组中的个数是否满足大于 N/3

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    class Solution {
        public List<Integer> majorityElement(int[] nums) {

            List<Integer> res = new ArrayList<>();
            if (nums == null || nums.length == 0) return res;

            // 初始化两个槽位以及其存储元素个数。
            //（为什么不定义三个槽位？ 有一个槽位必然用于抵消掉其他槽位，存储元素必是0，只需关注其他槽位存储情况即可）
            int slot1 = nums[0], count1 = 0;
            int slot2 = nums[0], count2 = 0;

            // 摩尔投票法
            // 入队槽和抵消过程
            for (int num : nums) {

                if (slot1 == num) { // 相同元素入相同的队槽
                    count1++;
                }else if (slot2 == num) { // 相同元素入相同的队槽
                    count2++;
                }else if (count1 == 0) { // 存储在候选空槽
                    slot1 = num;
                    count1++;
                }else if (count2 == 0) { // 存储在候选空槽
                    slot2 = num;
                    count2++;
                }else{      // 入最后剩余的空槽，且与其他槽发生一次抵消，此槽又变回空槽
                    count1--;
                    count2--;
                }

            }

            // 计数过程
            // 此时，获得剩下在队槽的元素，并数出对应元素在数组中的个数是否满足大于 N/3
            count1 = 0;
            count2 = 0;
            for (int num : nums) {
                if (slot1 == num) count1++;
                else if (slot2 == num) count2++;
            }

            if (count1 > nums.length / 3){
                res.add(slot1);
            }
            if (count2 > nums.length / 3){
                res.add(slot2);
            }

            return res;
        }

    }