Boyer Moore C++ O(n) time and O(1) space solution


#1
int Solution::majorityElement(const vector<int> &A) {
    
    if(A.size() == 1) return A[0];
    
    int count = 1;
    int check = A[0];
    
    
    for(int i = 1; i < A.size(); i++) {
        
        if(A[i] == check) count++;
        
        if(A[i] != check) count--;
        
        if(count == 0) {check = A[i]; count = 1;}
        
    }
    
    count = 0;
    
    for(int i = 0; i < A.size(); i++) {
        
        if(A[i] == check) count++;
    }
    
    if(count >= floor(A.size() / 2)) return check;
    else return -1;
    
}