Moorish voting

Moore voting (Boyer–Moore majority vote algorithm) From the paper
《MJRTYA Fast Ma jority
Vote Algorithm》
The problem solved by the algorithm is how to choose any number of candidates （ Ballot disorder ）, Choose the one who gets the most votes . The common algorithm is to scan the votes , Count the votes counted for each candidate . When the number of candidates is fixed , The time complexity of this common algorithm is ：O ( n ) , When the number of candidates varies , Counting votes may take a long time , May need to run O ( n^2 )
) Time for . When the votes are in order , It's easy to make up O ( n ) The program , First find the median , Then check whether the median number exceeds half of the vote . This paper aims at the situation of disorder and uncertain candidates , Moore voting algorithm is proposed . The maximum number of comparisons of the algorithm is votes （ Write it down as n） Twice as many , Can be in O ( n ) Choose the one who gets the most votes in time , The space cost is O ( 1 ) .

Visualize ：
The core is the cost of competition .

Play a game of princes fighting for supremacy , Suppose your population is more than half of the total population , And it can ensure that every population can die one-on-one when they go out to fight . In the end, the country where people survive is victory .
Scuffle time , Maybe everyone will unite against you （ Every time you choose as a counter, the number is mode ）, Or other countries will attack each other （ Other numbers will be selected as the number of counters ）, But as long as you don't fight inside , In the end, you're sure to win .
In the end, the rest must be our own people .

Algorithm application
One of the great applications of Moore voting is to find the mode .
Related topics are ：
1
Power button 169. Most elements

class Solution {
    
public:
    int majorityElement(vector<int>& nums) {
    
        int n = nums.size();
        int c = 1;
        int num = nums[0];
        for(int i = 1;i < n;i++)
        {
    
            if(num == nums[i])
                c++;
            else{
    
                c--;
                if(!c)
                    num = nums.at(i+1);
            }
        }
        return num;
    }
};

2
Power button 229. Find mode II
It can be seen as such a situation ： A class should elect a deputy monitor , at most 2 position . One vote for each , To become a vice squad leader, you must get more than one third of the total votes .
Because there may be two . So the candidate cand And counting cnt To the corresponding array form cands And cnts, The length is 2.
In the first stage, it is necessary to offset in pairs ,cands[0] And cands[1] Of the votes do not cancel each other out , That is, if the delegate votes for cands[0], be cands[1] Corresponding cnts[1] The value of does not change .
To vote for cands[1] The same is true . This translates into the original case of the Moorish voting method .
The second stage counts , In addition to determining whether two candidates have more than a third of the votes , It is also necessary to determine whether the two candidates are the same .

/*  The time complexity is ：O(n)  The space complexity is ：O(1) */
class Solution {
    
public:
    vector<int> majorityElement(vector<int>& nums) {
    
        int len = nums.size();
        vector<int>res, cands, cnts;
        if(len == 0){
    // There is no element , Returns an empty array directly 
            return res;
        }
        cands.assign(2, nums[0]);
        cnts.assign(2, 0);
        // The first 1 Stage   Set off in pairs 
        for(auto num: nums){
    
            bool flag = false;
            for(int i = 0; i < cands.size(); ++i){
    
                if(num == cands[i]){
    
                    ++cnts[i];
                    flag = true;
                    break;
                }
            }
            if(!flag){
    
                bool flag2 = false;
                for(int j = 0; j < cands.size(); ++j){
    
                    if(cnts[j] == 0){
    
                        flag2 = true;
                        cands[j] = num;
                        cnts[j]++;
                    }
                }
                if(!flag2){
    
                    for(int j = 0; j < cnts.size(); ++j){
    
                        --cnts[j];
                    }
                }
            }
        }

        // The first 2 Stage   Count   The number should be more than one third 
        cnts[0] = cnts[1] = 0;
        if(cands[0] == cands[1])
            cands.pop_back();
        for(auto num:nums){
    
            for(int i = 0; i < cands.size(); ++i){
    
                if(cands[i] == num){
    
                    ++cnts[i];
                    break;
                }
            }
        }
        for(int i = 0; i < cands.size(); ++i){
    
            if(cnts[i] > len / 3){
    
                res.push_back(cands[i]);
            }
        }
        return res;
    }
};

application 3
At most m A representative , The number of votes per ballot is greater than n / (m + 1)
Just put the question 2 Determine whether the final candidate is the same code for modification .