select algorithm to find element occurring more than n/2 in O(n)

Question

Without using Moore's algorithm or hash table, I need to find the element that occurs more than n/2 times in an array.

I know I have to use the select algorithm using median of median. I am confused as to what select algorithm returns because if it returns the median how am I sure the element occurs more than n/2 times in the array?

For example:

a [] = {4, 1, 5, 7, 8}

5 is the median but it doesn't occur more than n/2 times.

Now:

a[] = {5, 5, 3, 4, 5, 5}

In this case the median is 5 and it occurs more than n/2 times.

Answer 1

Use select algorithm to find the the median element. Here if the element is more than n/2 times it is obvious that it is the median. Use Median of median to get running time of O(n). The once you get the median element just count its occurrence in array which is again in linear time

Answer 2

I'd like to suggest another method. This problem is called "finding the leader" (at least in Polish literature). Let's call an element occuring more than n/2 times the leader of a sequence. The following observation is crucial - if there exists a leader in a sequence, after removing two different elements, the newly created sequence will have exactly the same leader as the original one. Why is that? If there is a leader, after removing two different elements, exactly one of them is the leader. The new sequence has n - 2 elements and more than (n / 2) - 1 occurences of the original leader, hence the original leader is the new leader. You repeat the deletion until all elements are equal. Then you can perform a linear check if the candidate is a leader.

Sample code (based on this article, unfortunately unavailable in English):

int leader = 0;
int number = 0; /* number of occurences of a leader candidate */
for (int k = 0; k < n; k++)
{
    if (number == 0)
    {
        //we set first element as a potential leader
        leader = a[k];
        number = 1;
    }
    else if (leader == a[k])
        //new leader occurence
        number++;
    else
        //delete two different elements
        number--;
}
//check if it really is the leader
number = 0;
for (int i = 0; i < n; i++)
    if (a[i] == leader)
        number++;
if (number > n / 2)
    System.out.println(leader);
else
    System.out.println("There is no leader");