[sword finger offer] interview question 39: numbers that appear more than half of the time in the array

Method 2 ： Record by index —— Moore voting

By recording a number times,
If the result of the current number and the next number are not equal , be times–
If it's the same times++
The last saved result is more than half of the number

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

    }

};

Method 3 ： Hash table lookup

class Solution {
    
public:
    int majorityElement(vector<int>& nums) {
    

        if( nums.size() == 0 )
            return 0;
        unordered_map<int,int> record;
        for( auto num : nums)
        {
    
            record[num]++;
            if( record[num] > (nums.size() / 2) )
                return num;
        }
        return 0;
    }

};