/*
problem: search majority element in an array
array: a[s...t]
majority element a[j]: the value of a[j] appears more than [n/2] times in array a
algorithm base:
1. for any array, there's at most one majority element
2. if majority element c exists, after deletion of two unequal elements in array, c will be the majority element in the remaining subarray all the same
3. if majority element doesn't exist, after deletion of two unequal elements in array, it's possible that there's a majority element in the remaining subarray
e.g, 1,2,3,3,3,4 no element appears more than three times after deletion of 1,2 in subarray 3,3,3,4 3 will be the majority element
conclusion:
after deletion of two unequal elements in original array, the majority element in the remaining subarray, if exists, will only be the candidate of the majority
element of original array. So make a check by traversing original array to make sure it's really a majority element of original array.
*/
int candidate( int * a, int s, int t )
{ //find majority element candidate of array a[s..t], if exist, return its first index, else, return -1
//we return index instead of value, to make difference between case i>t && count>0 and i>t && count=0
int c = a[s];
/* traverse from a[s+1] to a[t], if equal to c, increase count by one, else, decrease it by one. when count=0, search in subarray.
if reaches the end t and count>0, then c is a candidate of majority element of original array, return it. */
int count = 1;
`
if( i>t && count>0 ) //reach the end of array and count>0, it is a candidate
return s;
else if( i>t ) //reach the end of array and count=0, it's not a candidate
return -1;
else //count=0 and before the end, call it for subarray
return candidate( a, i, t );
}
int majority( int * a, int n )
{ // find real majority element of array a[0..n]
// return index of majority element if exists. else, return -1.
int i = candidate( a, 0, n );
if( i == -1 ) // no candidate
return -1;
int c = a[i]; //candidate
int count=0;
// check whether this candidate is a real majority element
for( int j=0; j<=n; ++j )
if( a[j] == c )
++count;
if( count > (n+1)/2 ) //real
return i;
else //fake
return -1;
}
/* complexity
time: O(n)
space: O(n) can use iteration to eliminate recursion
*/
