摩尔投票

绝地灬酷狼 2022-12-29 04:42 173阅读 0赞

# 摩尔投票 #

## 问题背景 ##

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

## 解决方案 ##

### 方案一 ###

我们可以使用一个容器对每位候选人的票数进行计数，然后查看每位候选人的总票数，就可以找到票数超过一半的候选人。  
在具体代码实现的时候，`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;
        }
    };

明天将对该算法的进阶进行叙述。晚安！！！

[leetcode169]: https://leetcode-cn.com/problems/majority-element/