摩尔投票法

有时候，刷算法题的关键是读懂题目。时常卡在读不懂题目=_=

摩尔投票法

今日的力扣每日一题是229.Majority Element II。看懂题目后最开始的想法就是普通的，遍历一遍数组统计出每个数字出现的次数存在数组中，然后再遍历一次数组找出是否存在次数大于⌊ n/3 ⌋的元素。

看了评论区题解学到了新的解题方法。刷题在于学习总结嘛。本题可以用到摩尔投票法的变体。

摩尔投票法出自论文，算法解决的问题是如何在任意多的候选人中，选出获得的票数最多的那个。算法演示，文章做了很详细的解读。摩尔投票法主要分为两个阶段，第一阶段筛选可能的元素，第二阶段验证。应用在众数的解答上。

Majority Element II 解答

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> res;
        int x = 0, y = 0; 
        int cx = 0, cy = 0;
        for(auto num : nums){
            if((cx == 0||num == x)&& num != y){
                cx++;
                x = num;
            }else if(cy == 0|| num == y){
                cy++;
                y = num;
            }else{
                cx--;
                cy--;
            }
        }
        int countx = 0, county = 0;
        for(auto num:nums){
            if(num == x) countx++;
            if(num == y) county++;
        }
        int target = nums.size()/3;
        if(countx > target) res.push_back(x);
        if(county > target && y != x) res.push_back(y);
        return res;
    }
};

参考博客

169 Majority Element 解答

前提条件中假设数组非空，且一定存在多数元素，所以可以省掉第二阶段验证。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int res = 0;
        int count = 0;
        for(auto num: nums){
            if(count == 0 || num == res){
                res = num;
                count++;
            }else{
                count--;
            }
        }       
        return res;
    }
};