摩尔投票-蒲公英云

摩尔投票

问题背景

在一个大厅中，每位票民手中都有一张票他可以给自己喜欢的候选人偷一票，我们现在已知每个票民的投票结果。
问：如何通过一次遍历找到票数超过一半的候选人。

解决方案

方案一

我们可以使用一个容器对每位候选人的票数进行计数，然后查看每位候选人的总票数，就可以找到票数超过一半的候选人。
在具体代码实现的时候，c++中可以使用一个map容器维护每位候选人的票数。
具体时间复杂度为O(n)，空间复杂度为O(m)，m为候选人的个数。

方案二

我们可以使用摩尔投票法求解。
摩尔投票法，解决的问题是如何在任意多的候选人中，选出票数超过一半的那个人。注意，是超出一半票数的那个人。
假设投票是这样的，[A, C, A, A, B]，ABC 是指三个候选人。
第一张票与第二张票进行对坑，如果票不同则互相抵消掉；
接着第三票与第四票进行对坑，如果票相同，则增加这个候选人的可抵消票数；
这个候选人拿着可抵消票数与第五张票对坑，如果票不同，则互相抵消掉，即候选人的可抵消票数 -1。

我们可以这样思考，我们可以选择每次选择两个人碰一下，如果他们的候选人不同，那么这两个人打一架然后出局，然后再选择两个人。如果两个人候选人是一伙的，那么他们在随机找一个人，如果不跟他们同一伙，那么他们两个人中一个人去跟那个人打架然后抵消掉即可。依次类推，最后剩下的人一定是一伙的，然后我们检测一下他们投的候选人是不是票数过半即可。如果最后没剩人，说明没有候选人票数过半。
关于应用，可以参考leetcode169

代码实现:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n=nums.size();
        int n1=0,nnum=0;
        for(auto &a:nums){
            if(nnum==0) {
    //此时没有选中人
                n1=a;     
                nnum++;
            }
            else if(a==n1) nnum++;
            else nnum--;
        }
        //题目说了有答案所以省去检测环节
        return n1;
    }
};