C++ solution voting Algo


  • 0
    S
    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            
            vector<int> res; 
            int cA=0;
            int cB=0;
            int a, b;
            int twoMaj=true;//there are two major elements
            
            for(int i=0;i<nums.size();i++){
                
                if(cA && a==nums[i]){
                    cA++;
                }else if(cB && b==nums[i]){
                    cB++;
                }else if(!cA){
                    a=nums[i];
                    cA++;
                }else if(!cB){
                    b=nums[i];
                    cB++;
                }else{
                    cA--;
                    cB--;
                }
            }
                    
                if(!cA && !cB){
                    return {};
                }
                if(!cB)
                    twoMaj=false;
                    
                cA=0,cB=0;
                
            for(int i=0;i<nums.size();i++){ 
                if(nums[i]==a)
                    cA++;
                if(twoMaj && nums[i]==b)
                    cB++;
                
            }
            
            
            if(cA>nums.size()/3)
                res.push_back(a);
            if(cB>nums.size()/3)
                res.push_back(b);
                
                
            return res;
            
        }
    };

Log in to reply
 

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