If we need to find a number that appears in more than half of the elements in an array, we can do so in O(n) time and O(1) space using the Boyer-Moore majority vote algorithm. We use a variable to keep track of a nominated number (nomnum) and another variable to keep track of a count for that number. We iterate through the array and for each number we do:
- If count is zero then set nomnum to the current array number and count to 1.
- Otherwise, if current array number == nomnum then we increment count.
- Otherwise decrement count.
Here’s a chart for an example run from wikipedia:
Here’s the c++ source code:
If we are not guaranteed to have a majority element then we can do a further pass of the array to determine if the nominated number is a majority element.
It is also possible to find up to two majority elements that appear more than n/3 times in an array. In the algorithm we use two nominated number variables and two counter variables. The key difference is that if the counts are not zero and the current array number is different from the current numbers then we need to decrement both counts. Here is the source code: