摩尔投票法（寻找众数）

• 问题1：在一个数组中找到一个出现次数大于n/2的数（保证一定存在）leetcode169题（多数元素）

  • 要求：实现时间复杂度为O(n)，空间复杂度为O(1)的解法
  • 解法：摩尔投票法

• 摩尔投票法：

  • 原理：当一个数在数组中出现次数大于n/2，那么每次删除两个不同的元素，剩下的元素一定是该数

  • 实现思路：

    • 要求时间复杂度O(n)，空间复杂度O(1)，因此不可能真的在数组中遍历并执行删除操作。
    • 其实现有一定技巧：假设存在一个虚拟数组，用于存放还未和不同元素一起删除的数，该数组只存在若干同一元素；遍历原数组，若有与虚拟数组元素不同的数，则会将两个数一起从虚拟数组中删去。
    • 因此只需要两个变量，一个存储可能是满足条件的值（虚拟数组中的数），一个存储个数。
    • 遍历原数组到当前元素时，若虚拟数组为空，则将当前数放入虚拟数组；若虚拟数组非空，则比较两数是否相同，若相同，则将当前数加入到虚拟数组；若不同，则虚拟数组的数减1，继续遍历下一元素（即相当于删除两数）。
    • 因为保证一定存储，所以最后虚拟数组剩下的数就是满足条件的“多数”。

  • leetcode代码：

    class Solution {
    public:
        /*摩尔投票法(寻找众数)*/
        int majorityElement(vector<int>& nums) {
            int candidate = -1;
            int cnt = 0;
            for (int num : nums) {
                if(cnt == 0)
                {
                    candidate = num;
                    cnt = 1;
                }
                else if(num == candidate) 
                    ++cnt;
                else    
                    --cnt;
            }
            return candidate;
        }
    };

• 问题2（进阶）：

  在一个数组中找到所有出现次数大于n/3的数 leetcode229题（求众数II）

  • 要求：实现时间复杂度为O(n)，空间复杂度为O(1)的解法

  • 问题分析：

    • 在一个数组中出现次数大于n/3的数最多有2个
    • 题目未说明保证存在满足条件的数

  • 思路：

    • 仍然是用摩尔投票法，只是因为没有保证该数存在，因此需要增加一个验证环节。
    • 最多可能有2个满足条件数，因此需要四个变量

    class Solution {
    public:
        /*摩尔投票法*/
        vector<int> majorityElement(vector<int>& nums) {
            int cnt1 = 0, cnt2 = 0;
            int can1 = 0, can2 = 0;
            for(int num:nums)
            {
                if(can1 == num)    
                    ++cnt1;
                else if(can2 == num)
                    ++cnt2;
                //candidate和cnt的判断不能交换顺序，否则可能为两个候选值赋为同一个值
                else if(cnt1 == 0)
                {
                    can1 = num;
                    cnt1 = 1;
                }
                else if(cnt2 == 0)
                {
                    can2 = num;
                    cnt2 = 1;
                }
                else
                {
                    --cnt1;
                    --cnt2;
                }
            }
            //验证是否满足条件
            vector<int> res;
            cnt1 = 0, cnt2 = 0;
            for(int num:nums)
            {
                if(can1 == num)
                    ++cnt1;
            //注意一定要用else if，保证两数的判断是有先后的，才不会出现两候选数相同的情况
                else if(can2 == num) 
                    ++cnt2;
            }
            if(cnt1 > nums.size()/3)
                res.emplace_back(can1);
            if(cnt2 > nums.size()/3)
                res.emplace_back(can2);
            return res;
        }
    };