Two best solution's


#1

first method uses the power of probability
since it is already mentioned in question that majority element is already present , then what is the probbility of choosing the a element at random to be a majority element , 1/2 exactly so is the same for no to be a majority element but if we increase our number of trial’s then our probability of getting a majrity element in one of our trial is very high , you can mathematically proove that tobe 99.99 percent sure of getting majority element we need only 15 trials , a goof thing about this technique is that you can generalise it to n/ k majority element you just need to find the number of trial required which is very bery easy

here is the code for this technioque

int Solution::majorityElement(const vector &A) {

int N = A.size(); 

int mji = 0 ; int cnt = 1 ; 

for( int i = 0 ; i < 15 ; i++ )
{
    int in = rand()%N ;
    
    int c = 0 ;
    for( auto x : A )
    {
        if( x == A[in] )c++ ;
        
        if( 2*c >= N  )return A[in];
    }
}

}

////////////////////////////////////////////

second technique is moor’s vooting algorithm which is pretty much standered algorithm every on knows that .

here is the code for it

int Solution::majorityElement(const vector &A) {

int N = A.size(); 

int mji = 0 ; int cnt = 1 ; 

for( int i = 1 ; i < N ; i++ )
{
    if( A[mji] == A[i] )cnt++ ;
    else cnt--;
    
    if( cnt == 0 )
    {
        mji = i ; 
        cnt = 1 ; 
    }
}

int c = 0 ;
for( auto x : A )
{
    if( x = A[mji] )c++; 
    
    if( 2*c >= N )
    {
        return A[mji];
    }
}

}