Moore Voting Algorithm


  • 0
    C
    class Solution {
    public:
        int majorityElement(vector<int>& nums) 
        {
            // Moore Voting Algorithm
            // find each pair of different values and delete them, 
            // then the remaining element is the majrity element
            // if the majority one may not exist, you should rescan the array to check its correctness
            
            int ele = nums[0];
            int cnt = 0;
            
            for(int i=0; i < nums.size(); i++)
            {
                if(nums[i] == ele)
                    cnt++;
                else if(cnt)
                    cnt--;
                else // cnt == 0
                    ele = nums[i];
            }
            
            return ele;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.