Leetcode-169. most elements

Mathematical problems

---

Topic details

Given a size of n Array of nums , Return most of the elements . Most elements refer to the number of occurrences in an array Greater than ⌊ n/2 ⌋ The elements of .
You can assume that the array is not empty , And there are always many elements in a given array .

---

Example 1：

 Input ：nums = [3,2,3]
 Output ：3

Example 2:

 Input ：nums = [2,2,1,1,1,2,2]
 Output ：2

Ideas :
An important point in the topic is that there must be many elements in a given array , That is, the number of occurrences in the array Greater than ⌊ n/2 ⌋ The elements of
Then this problem can be solved by Moore voting , Moore voting is traversing arrays , First set the first number to " The candidate " candidate, Then count the votes cnt’ Initialize to 1( Only his own vote ), Then walk back , If you encounter the same number , Just add tickets , Different numbers will be reduced , If the number of votes is reduced to 0 了 , Just change the next candidate , Continue traversing ( Note that the latter candidate may repeat the previous candidate , So you don't have to go back and traverse )
Then borrow the image description of a great God in the comment area about Moore voting :
Moore voting ：
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 .
That's a big scuffle , Worst of all, everyone's united 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 .

My code ：

class Solution 
{
    
public:
    int majorityElement(vector<int>& nums) 
    {
    
        int n = nums.size(), candidate = nums[0], cnt = 1;
        // Because of initialization candidate by nums[0] therefore i From you to 1 Start traversing 
        for (int i = 1; i < n; ++i) 
        {
    
            if (candidate == nums[i]) // If you encounter the same number 
            {
    
                ++cnt;               // Just " Add one vote "
            }
            else                     // Encountered different number 
            {
    
                --cnt;               // Just " Minus one vote "
                if (cnt == 0)        // After the ticket reduction, if there are no tickets 
                {
    
                // It means that the candidate's vote is definitely not greater than n/2 Of ( That is, not most elements ) 
                    candidate = nums[i]; // Then change the next candidate 
                    cnt = 1;             // The initial ticket is again 1 
                }
            }
        }
        return candidate;
    }
};